Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Wrong Answer

Solution code:
n, k, l = map(int, input().split())
con_k = [[] for _ in range(n)]
con_l = [[] for _ in range(n)]

group_k = [i for i in range(n)]
pqs = []
for _ in range(k):
    p, q = map(int, input().split())
    (p, q) = sorted((p, q))
    pqs.append((p, q))
for p, q in sorted(pqs):
    group_k[q-1] = group_k[p-1]

group_l = [i for i in range(n)]
srs = []
for _ in range(l):
    r, s = map(int, input().split())
    (r, s) = sorted((r, s))
    srs.append((r, s))
for s, r in sorted(srs):
    group_l[r-1] = group_l[s-1]

ans = [0] * n
for gk, gl in zip(group_k, group_l):
    for i in range(n):
        if gk == group_k[i] and gl == group_l[i]:
            ans[i] += 1

for a in ans:
    print(a, end=" ")

Submission status: Wrong Answer

Solution code:
n, k, l = map(int, input().split())
con_k = [[] for _ in range(n)]
con_l = [[] for _ in range(n)]

group_k = [i for i in range(n)]
for _ in range(k):
    p, q = map(int, input().split())
    (p, q) = sorted((p, q))
    group_k[q-1] = group_k[p-1]

group_l = [i for i in range(n)]
for _ in range(l):
    r, s = map(int, input().split())
    (r, s) = sorted((r, s))
    group_l[r-1] = group_l[s-1]

ans = [0] * n
for idx, (gk, gl) in enumerate(zip(group_k, group_l)):
    for i in range(n):
        if gk == group_k[i] and gl == group_l[i]:
            ans[i] += 1

for a in ans:
    print(a, end=" ")

Submission status: Wrong Answer

Solution code:
from itertools import product as prod

n, k, l = map(int, input().split())
con_k = [[] for _ in range(n)]
con_l = [[] for _ in range(n)]

group_k = [i for i in range(n)]
for _ in range(k):
    p, q = map(int, input().split())
    (p, q) = sorted((p, q))
    group_k[q-1] = group_k[p-1]

group_l = [i for i in range(n)]
for _ in range(l):
    r, s = map(int, input().split())
    (r, s) = sorted((r, s))
    group_l[r-1] = group_l[s-1]

group_kl = list(zip(group_k, group_l))
ans = [group_kl.count(kl) for kl in group_kl]
for a in ans:
    print(a, end=" ")

Submission status: Wrong Answer

Solution code:
from collections import deque


def create_group(N, n):
    city = [[] for _ in range(N + 1)]
    for _ in range(n):
        p, q = map(int, input().split(" "))
        city[p].append(q)
        city[q].append(p)

    group_list = [0] * (N + 1)
    gid = 0
    Q = deque()
    for i in range(1, N + 1):
        if group_list[i] == 0:
            gid += 1
            Q.clear()
            Q.append(i)
            group_list[i] = gid
            while len(Q) > 0:
                x = Q.popleft()
                for y in city[x]:
                    if group_list[y] == 0:
                        group_list[y] = gid
                        Q.append(y)

    return group_list

if __name__ == "__main__":
    N, K, L = list(map(int, input().split(" ")))
    rg = create_group(N, K)
    lg = create_group(N, L)

    rg_lg_dict = {}
    for i in range(1, N+1):
        key = (rg[i], lg[i])
        if key in rg_lg_dict:
            rg_lg_dict[key] += 1
        else:
            rg_lg_dict[key] = 1

    key = (rg[1], lg[1])
    print(rg_lg_dict[key], end='')
    for i in range(2, N+1):
        key = (rg[i], lg[i])
        print(rg_lg_dict[key], sep='', end='')

Submission status: Wrong Answer

Solution code:
from collections import deque


def create_group(N, n):
    city = [[] for _ in range(N + 1)]
    for _ in range(n):
        p, q = map(int, input().split(" "))
        city[p].append(q)
        city[q].append(p)
    group_list = [0] * (N + 1)
    gid = 0
    Q = deque()
    for i in range(1, N + 1):
        if group_list[i] == 0:
            gid += 1
            Q.clear()
            Q.append(i)
            group_list[i] = gid
            while len(Q) > 0:
                x = Q.popleft()
                for y in city[i]:
                    if group_list[y] == 0:
                        group_list[y] = gid
                        Q.append(y)

    return group_list

if __name__ == "__main__":
    N, K, L = list(map(int, input().split(" ")))
    rg = create_group(N, K)
    lg = create_group(N, L)
    
    rg_lg_dict = {}
    for i in range(1, N+1):
        key = (rg[i], lg[i])
        if key in rg_lg_dict:
            rg_lg_dict[key] += 1
        else:
            rg_lg_dict[key] = 1

    key = (rg[1], lg[1])
    print(rg_lg_dict[key], end='')
    for i in range(2, N+1):
        key = (rg[i], lg[i])
        print(rg_lg_dict[key], sep='', end='')

Submission status: Wrong Answer

Solution code:
class UnionFind:
	"""Union-Find, 
	http://www.slideshare.net/chokudai/union-find-49066733"""

	def __init__(self, N):
		self.par = [i for i in range(N)]

	def root(self, x):
		if(self.par[x]==x):
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

	def same(self, x, y):
		return self.par[x]==self.par[y]

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		# if x==y:
		# 	return
		self.par[x] = y
		return

N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

uf_k = UnionFind(N)
uf_l = UnionFind(N)

for i in range(K):
	uf_k.unite(P[i]-1, Q[i]-1)
for i in range(L):
	uf_l.unite(R[i]-1, S[i]-1)

k_groups = [uf_k.root(i) for i in range(N)]
l_groups = [uf_l.root(i) for i in range(N)]

kl_groups = [(k_groups[i], l_groups[i]) for i in range(N)]
kl_groups_origin = kl_groups
kl_groups = sorted(kl_groups)

results_dict = {}

idx = 0
count = 1
pair = kl_groups[0]
for i in range(1, N):
	if kl_groups[i]==pair:
		count = count+1
	else:
		results_dict[pair] = count
		pair = kl_groups[i]
		count = 1
results_dict[pair] = count

print(results_dict)

for i in range(N):
	pair = kl_groups_origin[i]
	print(results_dict[pair], end=" ")

Submission status: Wrong Answer

Solution code:
N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

k_groups = [i+1 for i in range(N)]
l_groups = [i+1 for i in range(N)]

for i in range(K):
	k_groups[Q[i]-1] = k_groups[P[i]-1]
for i in range(L):
	l_groups[S[i]-1] = l_groups[R[i]-1]

# num_kg = max(k_groups)
# num_lg = max(l_groups)

kl_list = [(k_groups[i], l_groups[i]) for i in range(N)]
for i in range(N):
	kl = kl_list[i]
	count = 0
	for j in range(N):
		if kl_list[j]==kl:
			count = count+1
	print(count, end=" ")

Submission status: Wrong Answer

Solution code:

import numpy as np

N, K, L =map(int,input().split())



city_street = np.arange(-1,-1*(N+1),-1)
num_street = 0
for i in range(0,K):
    #pi,qi = streets[i]
    pi,qi = map(int,input().split())
    pi  -= 1
    qi  -= 1
    if city_street[pi] * city_street[qi] < 0:
        city_street[pi] =  city_street[qi] = max(city_street[pi],city_street[qi])
    else:
        num_street +=1
        city_street[pi] =  city_street[qi] = num_street
        


city_rail = np.arange(-1,-1*(N+1),-1)
num_rail = 0
for i in range(0,K):
    #ri,si = rails[i]
    ri,si  = map(int,input().split())
    ri  -= 1
    si  -= 1
    if city_rail[ri] * city_rail[si] < 0:
        city_rail[ri] =  city_rail[si] = max(city_rail[ri],city_rail[si])
    else:
        if city_rail[ri] < 0:
            num_rail +=1
            city_rail[ri] =  city_rail[si] = num_rail
            

answers = []
for (i,num_street) in enumerate(city_street):
    temp_city_rail = city_rail +(city_street[i]- city_rail[i])
    print(temp_city_rail," ",city_street)
    rail_index = np.where(temp_city_rail == city_street[i])
    street_index = np.where(city_street == city_street[i])
    print("indixes",rail_index,street_index)
    array = np.in1d(rail_index,street_index).tolist()
    print(array)
    answers.append(array.count(True))
     
print(str(answers).replace(',',' ')[1:-1])

Submission status: Wrong Answer

Solution code:
from itertools import chain
n,r1,r2=map(int,input().split())
road=set(chain.from_iterable([input().split() for i in range(r1)]))
rail=set(chain.from_iterable([input().split() for i in range(r2)]))
do = road & rail
print(" ".join(["2" if str(i) in do  else "1"  for i in range(1,n+1)]))

Submission status: Wrong Answer

Solution code:
n,k,l = map(int, input().split())
def f(m):
    a = [[] for _ in range(n)]
    for _ in range(m):
        p,q = map(int, input().split())
        a[p-1].append(q-1)
    b = list(range(n))
    def g(i,j):
        if b[j] != j:
            return
        b[j] = i
        for k in a[j]:
            g(i, k)
    for i in range(n):
        g(i,i)
    return b
a = f(k)
b = f(l)
d = {}
for i in range(n):
    d.setdefault((a[i],b[i]), []).append(i)
c = [1]*n
for s in d.values():
    for i in s:
        c[i] = len(s)
print(' '.join(map(str, c)))

Submission status: Wrong Answer

Solution code:
n,k,l = [int(i) for i in input().split()]
ar = [0 for i in range(n)] #road id list
br = [0 for i in range(n)] #train id list
counter = 1 #0 is for initial state.
for road in range(k):
    p, q = [int(i) for i in input().split()]
    p -= 1
    q -= 1
    if ar[p] != 0:
        ar[q] = ar[p]
    elif ar[q] != 0:
        ar[p] = ar[q]
    else:
        ar[p] = counter
        ar[q] = counter
        counter += 1
    # print(ar)

counter = 1
for train in range(l):
    r, s = [int(i) for i in input().split()]
    r -= 1
    s -= 1
    if br[r] != 0:
        br[s] = br[r]
    elif br[s] != 0:
        br[r] = br[s]
    else:
        br[r] = counter
        br[s] = counter
        counter += 1
    # print(br)

Submission status: Wrong Answer

Solution code:
n,k,l = [int(i) for i in input().split()]
ar = [0 for i in range(n)] #road id list
br = [0 for i in range(n)] #train id list
counter = 1 #0 is for initial state.
for road in range(k):
    p, q = [int(i) for i in input().split()]
    p -= 1
    q -= 1
    if ar[p] != 0:
        ar[q] = ar[p]
    elif ar[q] != 0:
        ar[p] = ar[q]
    else:
        ar[p] = counter
        ar[q] = counter
        counter += 1
    # print(ar)

counter = 1
for train in range(l):
    r, s = [int(i) for i in input().split()]
    r -= 1
    s -= 1
    if br[r] != 0:
        br[s] = br[r]
    elif br[s] != 0:
        br[r] = br[s]
    else:
        br[r] = counter
        br[s] = counter
        counter += 1
    # print(br)

out = ""
cities = [(ar[i],br[i]) for i in range(n)]
for city in cities:
    if city[0] == 0 or city[1] == 0:
        out += "1 "
        continue
    out += str(cities.count(city)) + " "
print(out)

Submission status: Wrong Answer

Solution code:
n,k,l = [int(i) for i in input().split()]
ar = [0 for i in range(n)] #road id list
br = [0 for i in range(n)] #train id list
counter = 1 #0 is for initial state.
for road in range(k):
    p, q = [int(i) for i in input().split()]
    p -= 1
    q -= 1
    if ar[p] != 0:
        ar[q] = ar[p]
    elif ar[q] != 0:
        ar[p] = ar[q]
    else:
        ar[p] = counter
        ar[q] = counter
        counter += 1
    print(ar)

counter = 1
for train in range(l):
    r, s = [int(i) for i in input().split()]
    r -= 1
    s -= 1
    if br[r] != 0:
        br[s] = br[r]
    elif br[s] != 0:
        br[r] = br[s]
    else:
        br[r] = counter
        br[s] = counter
        counter += 1
    print(br)

out = ""
cities = [(ar[i],br[i]) for i in range(n)]
for city in cities:
    if city[0] == 0 or city[1] == 0:
        out += "1 "
        continue
    out += str(cities.count(city)) + " "
print(out)

Submission status: Wrong Answer

Solution code:
#cording : utf-8

def listin(l,ary):
    for i in range(2):
        ary[int(str(l).split(" ",1)[i])-1] = 1
    return ary

n,k,l = map(int,str(input()).split(" ",2))
array = [0 for i in range(n)]
array2 = [0 for i in range(n)]

for i in range(k):
    listin(input(),array)
for i in range(l):
    listin(input(),array2)

for k in range(n):
    print(array[k]+array2[k],end=' ')

Submission status: Wrong Answer

Solution code:
n,k,l = map(int, input().split())
a = [0]*(n+1)
b = [0]*(n+1)
u = iter(range(1, k+l+1))
def f(a, k):
    for _ in range(k):
        p,q = map(int, input().split())
        a[p] = a[q] = a[p] or a[q] or next(u)
f(a, k)
f(b, l)
d = {}
for i in range(1, n+1):
    if a[i] and b[i]:
        d.setdefault((a[i],b[i]), []).append(i)
c = [1]*(n+1)
for k in d:
    for i in d[k]:
        c[i] = len(d[k])
print(' '.join(map(str, c[1:])))

Submission status: Wrong Answer

Solution code:
n,k,l = map(int, input().split())
a = [0]*(n+1)
b = [0]*(n+1)
u = iter(range(k+l))
def f(a, k):
    for _ in range(k):
        p,q = map(int, input().split())
        a[p] = a[q] = a[p] or a[q] or next(u)
f(a, k)
f(b, l)
d = {}
for i in range(1, n+1):
    if a[i] and b[i]:
        d.setdefault((a[i],b[i]), []).append(i)
c = [1]*(n+1)
for k in d:
    for i in d[k]:
        c[i] = len(d[k])
print(' '.join(map(str, c[1:])))

Submission status: Wrong Answer

Solution code:
n,k,l = map(int, input().split())
a = [0]*(n+1)
b = [0]*(n+1)
u = iter(range(k+l))
def f(a, k):
    for _ in range(k):
        p,q = map(int, input().split())
        a[p] = a[q] = a[p] or a[q] or next(u)
f(a, k)
f(b, l)
d = {}
for i in range(1, n+1):
    if a[i] and b[i]:
        d.setdefault((a[i],b[i]), []).append(i)
c = [1]*(n+1)
for k in d:
    for i in d[k]:
        for i in d[k]:
            c[i] = len(d[k])
print(' '.join(map(str, c[1:])))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent, parent[x])
        return parent[x]

def union(parent, x, y):
    parent_x = find(parent, x)
    parent_y = find(parent, y)

    if parent_x != parent_y:
        parent[y] = parent[x]

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent, parent[x])
        return parent[x]

def union(parent, x, y):
    parent_x = find(parent, x)
    parent_y = find(parent, y)

    if parent_x != parent_y:
        parent[y] = x

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [i for i in xrange(n)]
        railways = [i for i in xrange(n)]

        for i in xrange(k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if roads[y - 1] > roads[x - 1]:
                roads[y - 1] = roads[x - 1]
            else:
                roads[x - 1] = roads[y - 1]

        for i in xrange(l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if railways[y - 1] > railways[x - 1]:
                railways[y - 1] = railways[x - 1]
            else:
                railways[x - 1] = railways[y - 1]

        table_roads = {}
        table_railways = {}
        for i in xrange(n):
            if not table_roads.has_key(roads[i]):
                table_roads[roads[i]] = set()
            table_roads[roads[i]].add(i)
            if not table_railways.has_key(railways[i]):
                table_railways[railways[i]] = set()
            table_railways[railways[i]].add(i)

        results = []
        for i in xrange(n):
            results.append(str(len(
              table_roads[roads[i]].intersection(table_railways[railways[i]]))))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")

if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
n,k,l = map(int,input().split())
road_list,train_list,c = [],[],[]
for _ in range(k) :
	road_list.append(list(map(int,input().split())))
for _ in range(l) :
	train_list.append(list(map(int,input().split())))
for _ in range(n) :
	c.append(0)

road_all,train_all = [],[] 
for i in road_list :
	road_all.append(i[0])
	road_all.append(i[1])
for i in train_list :
	train_all.append(i[0])
	train_all.append(i[1])

or_1 = list(set(road_all).union(set(train_all)))
and_2 = list(set(road_all).intersection(set(train_all)))

for i in or_1 :
	c[i-1] = 1
for j in and_2 :
	c[j-1] = 2
print(" ".join(map(str,c)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [i for i in xrange(n)]
        railways = [i for i in xrange(n)]

        for i in xrange(k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if roads[y - 1] > roads[x - 1]:
                roads[y - 1] = roads[x - 1]

        for i in xrange(l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if railways[y - 1] > railways[x - 1]:
                railways[y - 1] = railways[x - 1]

        for i in xrange(n):
            if roads[i] != i:
                roads[i] = roads[roads[i]]
            if railways[i] != i:
                railways[i] = railways[railways[i]]

        results = [0 for i in xrange(n)]
        for i in xrange(n):
            for j in xrange(n):
                if roads[i] == roads[j] and railways[i] == railways[j]:
                    results[i] += 1
        results = map(lambda r: str(r), results)
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [i for i in xrange(n)]
        railways = [i for i in xrange(n)]

        for i in xrange(k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if roads[y - 1] > roads[x - 1]:
                roads[y - 1] = roads[x - 1]

        for i in xrange(l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if railways[y - 1] > railways[x - 1]:
                railways[y - 1] = railways[x - 1]

        results = [0 for i in xrange(n)]
        for i in xrange(n):
            for j in xrange(n):
                if roads[i] == roads[j] and railways[i] == railways[j]:
                    results[i] += 1
        results = map(lambda r: str(r), results)
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [i for i in xrange(n)]
        railways = [i for i in xrange(n)]

        for i in xrange(k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if roads[y - 1] > roads[x - 1]:
                roads[y - 1] = roads[x - 1]

        for i in xrange(l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if railways[y - 1] > railways[x - 1]:
                railways[y - 1] = railways[x - 1]

        print roads
        print railways
        results = [0 for i in xrange(n)]
        for i in xrange(n):
            for j in xrange(n):
                if roads[i] == roads[j] and railways[i] == railways[j]:
                    results[i] += 1
        results = map(lambda r: str(r), results)
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
passed=set([])
def search(goal,path,adj):
    global passed
    n=path[-1]
    if goal==n:
        passed=passed.union(path)
        print passed
    else:
        for x in adj[n]:
            if x not in path:
                path.append(x)
                search(goal,path,adj)
                path.pop()
    
adj_r=[]
adj_t=[]
passed_r=[]
passed_t=[]
N,K,L=map(int,raw_input().split())

for _ in range(0,N):
    adj_r.append(set())
    adj_t.append(set())
    passed_r.append(set())
    passed_t.append(set())


max_len=N-1

for _ in range(0,K):
    p=map(int,raw_input().split())
    adj_r[p[0]-1].add(p[1]-1)
    adj_r[p[1]-1].add(p[0]-1)

for _ in range(0,L):
    p=map(int,raw_input().split())
    adj_t[p[0]-1].add(p[1]-1)
    adj_t[p[1]-1].add(p[0]-1)
for i in range(0,N):
    for j in range(0,N):
        search(j,[i],adj_r)
        passed_r[i]=passed_r[i].union(passed)
        passed=set([])
        search(j,[i],adj_t)
        passed_t[i]=passed_t[i].union(passed)
        passed=set([])
print passed_r
print passed_t

for (r,t) in zip(passed_r,passed_t):
    print len(r&t),
    

print ""

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [set([i]) for i in xrange(n)]
        railways = [set([i]) for i in xrange(n)]

        for i in xrange(0, k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            roads[x - 1].update(roads[y - 1])
            roads[y - 1] = roads[x - 1]

        for i in xrange(0, l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            railways[x - 1].update(railways[y - 1])
            railways[y - 1] = railways[x - 1]

        results = []
        for i in xrange(0, n):
            results.append(str(len(roads[i].intersection(railways[i]))))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [set([i]) for i in xrange(n)]
        railways = [set([i]) for i in xrange(n)]

        for i in xrange(0, k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            roads[x - 1].add(y - 1)
            roads[y - 1] = roads[x - 1]

        for i in xrange(0, l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            railways[x - 1].add(y - 1)
            railways[y - 1] = railways[x - 1]

        results = []
        for i in xrange(0, n):
            results.append(str(len(roads[i].intersection(railways[i]))))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [set([i]) for i in xrange(n)]
        railways = [set([i]) for i in xrange(n)]

        for i in xrange(0, k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            u = roads[x - 1].union(roads[y - 1])
            roads[x - 1] = u
            roads[y - 1] = u

        for i in xrange(0, l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            u = railways[x - 1].union(railways[y - 1])
            railways[x - 1] = u
            railways[y - 1] = u

        results = []
        for i in xrange(0, n):
            results.append(str(len(roads[i].intersection(railways[i]))))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
N, K, L = list(map(int, input().split(" ")))
N += 1

n_rl = [[[], [], None] for _ in range(N)]

for _ in range(K):
    p, q = list(map(int, input().split(" ")))
    for i in n_rl[p][0]:
        n_rl[i][0].append(q)
        n_rl[q][0].append(i)
    n_rl[p][0].append(q)
    n_rl[q][0].append(p)

for _ in range(L):
    r, s = list(map(int, input().split(" ")))
    for i in n_rl[r][1]:
        n_rl[i][1].append(s)
        n_rl[s][1].append(i)
    n_rl[r][1].append(s)
    n_rl[s][1].append(r)

for rl in n_rl[1:]:
    r_set = set(rl[0])
    l_set = set(rl[1])
    intersection = r_set.intersection(l_set)
    print("{} ".format(len(intersection) + 1), end="")

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split() )
doro=[]
senro=[]

for i in range(K):
    a,b=map(int, input().split())
    doro.append([a,b])

for i in range(L):
    a,b=map(int, input().split())
    senro.append([a,b])


def sab_d(a,b):
    for x in Doro[b-1]:
        if (x in Doro[a-1])==False:
            Doro[a-1].append(x)
    for y in Doro[a-1]:
        if (y in Doro[b-1])==False:
            Doro[b-1].append(y)
    return()

def sab_s(a,b):
    for x in Senro[b]:
        if (x in Senro[a])==False:
            Senro[a].append(x)
    for y in Senro[a]:
        if (y in Senro[b])==False:
            Senro[b].append(y)
    return()


Doro=[]
Senro=[]

for i in range(N):
    Doro.append([i+1])
for i in range(N):
    Senro.append([i+1])


for i in range(K):
    a=doro[i][0]
    b=doro[i][1]
    sab_d(a,b)

for i in range(L):
    a=senro[i][0]
    b=senro[i][1]
    sab_s(a,b)



result = []

for i in range(N):
    count=0
    a=Doro[i]
    b=Senro[i]
    for j in a:
        if (j in b)==True:
            count += 1 
    result.append(count)

for i in range(N):
    print(result[i],end=" ")

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,raw_input().split())
d=dict()
for i in range(n):
    d[i+1]=[]
for i in range(n):
    a,b=map(int,raw_input().split())
    c=d[a]
    c.append(b)
    d[a]=list(set(c))

    e=d[b]
    e.append(a)
    d[b]=list(set(e))
k=d.keys()
for j in k:
    a=d[j]
    print len(a),

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
roads=[{i} for i in range(n+1)]
rails=[{i} for i in range(n+1)]
for i in range(k):
    a,b=map(int,input().split())
    roads[a].add(b)
    roads[b].add(a)

for i in range(l):
    a,b=map(int,input().split())
    rails[a].add(b)
    rails[b].add(a)

for i in range(1,n):
    print(len(roads[i]&rails[i]),end=" ")
print(len(roads[n]&rails[n]))

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
roads=[[i] for i in range(n+1)]
rails=[[i] for i in range(n+1)]
for i in range(k):
    a,b=map(int,input().split())
    roads[a].append(b)
    roads[b].append(a)

for i in range(l):
    a,b=map(int,input().split())
    rails[a].append(b)
    rails[b].append(a)

for i in range(1,n):
    print(len(set(roads[i])&set(rails[i])),end=" ")
print(len(set(roads[n])&set(rails[n])))

Submission status: Wrong Answer

Solution code:
n, k, l = [int(x) for x in raw_input().split()]
d = [[set([i]), set([i])] for i in range(n)]
for i in range(k):
    p, q = [int(x) - 1 for x in raw_input().split()]
    d[p][0] |= d[q][0]
    d[q][0] = d[p][0]
for i in range(l):
    r, s = [int(x) - 1 for x in raw_input().split()]
    d[r][1] |= d[s][1]
    d[s][1] = d[r][1]
for s1, s2 in d:
    print len(s1 & s2),