Submission #6389755


Source Code Expand

Copy
#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

Submission Time
Task B - Even Degrees
User priyam2k
Language PyPy2 (5.6.0)
Score 0
Code Size 2916 Byte
Status RE
Exec Time 39 ms
Memory 28012 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
RE × 2
RE × 36
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt RE 39 ms 27884 KB
02.txt RE 38 ms 25964 KB
03.txt RE 38 ms 26988 KB
04.txt RE 37 ms 26348 KB
05.txt RE 38 ms 27372 KB
06.txt RE 38 ms 28012 KB
07.txt RE 38 ms 26988 KB
08.txt RE 38 ms 26732 KB
09.txt RE 38 ms 26860 KB
10.txt RE 38 ms 27756 KB
11.txt RE 38 ms 27756 KB
12.txt RE 38 ms 26732 KB
13.txt RE 38 ms 27372 KB
14.txt RE 38 ms 27500 KB
15.txt RE 39 ms 27756 KB
16.txt RE 38 ms 25964 KB
17.txt RE 38 ms 27116 KB
18.txt RE 38 ms 26476 KB
19.txt RE 38 ms 26604 KB
20.txt RE 38 ms 26348 KB
21.txt RE 38 ms 27372 KB
22.txt RE 38 ms 26604 KB
23.txt RE 37 ms 26348 KB
24.txt RE 39 ms 27756 KB
25.txt RE 39 ms 27884 KB
26.txt RE 38 ms 27756 KB
27.txt RE 38 ms 27884 KB
28.txt RE 38 ms 26732 KB
29.txt RE 39 ms 27756 KB
30.txt RE 38 ms 26988 KB
31.txt RE 39 ms 28012 KB
32.txt RE 39 ms 27756 KB
33.txt RE 39 ms 27884 KB
34.txt RE 39 ms 27756 KB
s1.txt RE 38 ms 27116 KB
s2.txt RE 38 ms 27116 KB