Submission #6389754

---

Source Code Expand

#import resource
import sys
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
import threading
threading.stack_size(2**25)
sys.setrecursionlimit(10**6)
mod=(10**9)+7
fact=[1]
#for i in range(1,1001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*1001
#ifact[1000]=pow(fact[1000],mod-2,mod)
#for i in range(1000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import math
import heapq
#from random import randint as rn
from Queue import Queue as Q
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def GCD(x, y):
   while(y):
       x, y = y, x % y
   return x
def isprime(x):
    p=int(math.sqrt(x))+1
    if(x==1):
        return 0
    for i in range(2,p):
        if(x%p==0):
            return 0
    return 1
"""**************************************************************************"""
def main():
    def find(x):
        if(p[x]!=x):
            x=find(p[x])
        return p[x]
    def union(u,v):
        a=find(u)
        b=find(v)
        if(r[a]>r[b]):
            p[b]=a
        elif(r[a]<r[b]):
            p[a]=b
        else:
            p[b]=a
            r[a]+=1
    def dfs(x,y):
        if(p[x]==0):
            p[x]=1
            for i in b1[x]:
                dfs(i,x)
            if(x!=0):
                if(deg[x]%2!=0):
                    t=1
                    deg[x]+=1
                else:
                    t=0
                    deg[y]+=1
                if(c.has_key((x,y))==True):
                    if(t==1):
                        ans[c[(x,y)]]=1
                else:
                    if(t==0):
                        ans[c[(y,x)]]=1
    for _ in range(1):
        n,m=ain()
        b=[]
        r=[0]*n
        p=[i for i in range(n)]
        for i in range(m):
            x,y=ain()
            b.append((x-1,y-1))
        q=n-1
        c={}
        b1=[[] for i in range(n)]
        i=0
        while(q>0):
            g=find(b[i][0])
            h=find(b[i][1])
            if(g!=h):
                q-=1
                c[b[i]]=i
                b1[b[i][0]].append(b[i][1])
                b1[b[i][1]].append(b[i][0])
                union(b[i][0],b[i][1])
            i+=1
        deg=[0]*n
        ans=[0]*m
        for i in range(m):
            if(c.has_key(b[i])==False):
                deg[b[i][1]]+=1
        p=[0]*n
        dfs(0,-1)
        if(deg[0]%2==1):
            print -1
            continue
        else:
            for i in range(m):
                print ans[i],
            print
threading.Thread(target=main).start()

Submission Info

Judge Result