Submission #6389748


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(input()):
        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 2921 Byte
Status WA
Exec Time 55 ms
Memory 32872 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
WA × 2
WA × 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 WA 55 ms 30184 KB
02.txt WA 38 ms 29544 KB
03.txt WA 38 ms 29672 KB
04.txt WA 38 ms 29928 KB
05.txt WA 39 ms 30056 KB
06.txt WA 39 ms 30568 KB
07.txt WA 39 ms 30312 KB
08.txt WA 39 ms 29800 KB
09.txt WA 39 ms 29416 KB
10.txt WA 39 ms 29928 KB
11.txt WA 39 ms 30312 KB
12.txt WA 39 ms 31464 KB
13.txt WA 39 ms 31080 KB
14.txt WA 38 ms 29672 KB
15.txt WA 39 ms 29928 KB
16.txt WA 39 ms 30184 KB
17.txt WA 38 ms 29800 KB
18.txt WA 38 ms 31336 KB
19.txt WA 39 ms 30312 KB
20.txt WA 38 ms 29672 KB
21.txt WA 38 ms 30056 KB
22.txt WA 39 ms 30056 KB
23.txt WA 39 ms 31208 KB
24.txt WA 38 ms 30952 KB
25.txt WA 39 ms 30568 KB
26.txt WA 38 ms 30312 KB
27.txt WA 39 ms 29928 KB
28.txt WA 38 ms 31336 KB
29.txt WA 38 ms 29928 KB
30.txt WA 38 ms 30952 KB
31.txt WA 38 ms 29672 KB
32.txt WA 38 ms 29672 KB
33.txt WA 38 ms 32872 KB
34.txt WA 39 ms 30568 KB
s1.txt WA 38 ms 31080 KB
s2.txt WA 38 ms 29544 KB