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: Runtime Error

Solution code:
N,K,L = map(int,input().split())
roads = [list(map(int,input().split())) for _ in range(K)]
rails = [list(map(int,input().split())) for _ in range(L)]
outputs = [1 for _ in range(N)]

class UF():
  def __init__(self,size):
    self.table = [-1 for _ in range(size)]
    self.results = {}
    
  def find(self,x):
    target = x
    while self.table[x] >= 0:
      x = self.table[x]
    if 0 < self.table[target] and self.table[target] != x:
      self.table[target] = x
    return x
  
  def union(self,x,y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s1] < self.table[s2]:
        self.table[s2] = s1
        if s2 in self.results:
          self.results[s1].add(self.results[s2])
          self.results.delete(s2)
        else:
          self.results[s1].add(s2)
      else:
        self.table[s1] = s2
        self.table[s2] -= 1
        if s1 in self.results and s2 in self.results:
          self.results[s2].add(self.results[s1])
          self.results.delete(s1)
        elif s2 in self.results:
          self.results[s2].add(s1)
        else:
          self.results[s2] = set([s1,s2])
    return

w = UF(N+1)

for r in roads:
  w.union(r[0],r[1])

t = UF(N+1)
for l in rails:
  t.union(l[0],l[1])

for x in range(1,N+1):
  if w.find(x) in w.results and t.find(x) in t.results:
    outputs[x-1] = len(w.results[w.find(x)] & t.results[t.find(x)])
  else:
    outputs[x-1] = 1
print(' '.join(map(str,outputs)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000)

n, k, l = map(int, input().split())
a = [list() for _ in range(n)]
b = [list() for _ in range(n)]
for _ in range(k):
    p, q = [int(x) - 1 for x in input().split()]
    a[p].append(q)
    a[q].append(p)
for _ in range(l):
    r, s = [int(x) - 1 for x in input().split()]
    b[r].append(s)
    b[s].append(r)

def g(a, b, i, k):
    b[i] = k
    for e in a[i]:
        if b[e] is not None: continue
        g(a, b, e, k)

def f(a, b):
    k = 0
    for i in range(n):
        if b[i] is not None: continue
        g(a, b, i, k)
        k += 1

c = [None] * n
f(a, c)
d = [None] * n
f(b, d)
e = {}
for i in range(n):
    k = (c[i], d[i])
    e[k] = e.get(k, 0) + 1

print(' '.join([str(e[(c[i], d[i])]) for i in range(n)]))

Submission status: Runtime Error

Solution code:
n, k, l = map(int, input().split())
a = [list() for _ in range(n)]
b = [list() for _ in range(n)]
for _ in range(k):
    p, q = [int(x) - 1 for x in input().split()]
    a[p].append(q)
    a[q].append(p)
for _ in range(l):
    r, s = [int(x) - 1 for x in input().split()]
    b[r].append(s)
    b[s].append(r)

def g(a, b, i, k):
    b[i] = k
    for e in a[i]:
        if b[e] is not None: continue
        g(a, b, e, k)

def f(a, b):
    k = 0
    for i in range(n):
        if b[i] is not None: continue
        g(a, b, i, k)
        k += 1

c = [None] * n
f(a, c)
d = [None] * n
f(b, d)
e = {}
for i in range(n):
    k = (c[i], d[i])
    e[k] = e.get(k, 0) + 1

print(' '.join([str(e[(c[i], d[i])]) for i in range(n)]))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

def root(n, tree):
    if tree[n] == n:
        return n
    else:
        tree[n] = root(tree[n], tree)
        return tree[n]

n, k, l = map(int, input().split())
road = [i for i in range(n+1)]
railway = [i for i in range(n+1)]
tree = [i for i in range(n+1)]
for _ in range(k):
    p, q = map(int, input().split())
    road[p] = q
for _ in range(k):
    p, q = map(int, input().split())
    railway[p] = q

from itertools import combinations

for p, q in combinations(range(1,n+1), 2):
    if (root(p, road) == root(q, road)) and (root(p, railway) == root(q, railway)):
        tree[p] = q

count = [0 for _ in range(n+1)]
for i in range(1,n+1):
    count[root(i, tree)] += 1

for i in range(1,n):
    print(count[root(tree[i], tree)], end=' ')
print(count[root(tree[n], tree)], end='')

Submission status: Runtime Error

Solution code:
def root(n, tree):
    if tree[n] == n:
        return n
    else:
        tree[n] = root(tree[n], tree)
        return tree[n]

n, k, l = map(int, input().split())
road = [i for i in range(n+1)]
railway = [i for i in range(n+1)]
tree = [i for i in range(n+1)]
for _ in range(k):
    p, q = map(int, input().split())
    road[p] = q
for _ in range(k):
    p, q = map(int, input().split())
    railway[p] = q

from itertools import combinations

for p, q in combinations(range(1,n+1), 2):
    if (root(p, road) == root(q, road)) and (root(p, railway) == root(q, railway)):
        tree[p] = q

count = [0 for _ in range(n+1)]
for i in range(1,n+1):
    count[root(i, tree)] += 1

for i in range(1,n):
    print(count[root(tree[i], tree)], end=' ')
print(count[root(tree[n], tree)], end='')

Submission status: Runtime Error

Solution code:
class uf_tree:
    def __init__(self, n):
        self.sizes = [0] * n
        self.par = range(n)

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[find(x)]


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

uf_1 = uf_tree(N+1)
uf_2 = uf_tree(N+1)

for i in range(K):
    p, q = map(int, raw_input().split())
    uf_1.unite(p, q)

for i in range(L):
    r, s = map(int, raw_input().split())
    uf_2.unite(r, s);

dic = {}
for i in range(1, N+1):
    key = (uf_1.find(i), uf_2.find(i))
    dic[key] = dic.get(key, 0) + 1

for i in range(1, N+1):
    print dic[(d.find(i), t.find(i))],

Submission status: Runtime Error

Solution code:

N,K,L=map(int,input().split())
road=[[0]*N for i in range(N)]
train=[[0]*N for j in range(N)]

for i in range(K):
    p,q=map(int,input().split())
    road[p-1][q-1]=1
    road[q-1][p-1]=1
for j in range(L):
    r,s=map(int,input().split())
    train[r-1][s-1]=1
    train[s-1][r-1]=1


def count_r(node,visited):
    visited[node]=1
    ans=sum(visited)
    rt_visited=visited
    for i in range(N):
        if not visited[i] and road[node][i]:
            visited[i]=1
            rc_visited=count_r(i,visited)
            c_cnt=sum(rc_visited)
            if ans<c_cnt:
                ans=c_cnt
                rt_visited=rc_visited
    return rt_visited

def count_t(node,visited):
    visited[node]=1
    ans=sum(visited)
    rt_visited=visited
    for i in range(N):
        if not visited[i] and train[node][i]:
            visited[i]=1
            rc_visited=count_t(i,visited)
            c_cnt=sum(rc_visited)
            if ans<c_cnt:
                ans=c_cnt
                rt_visited=rc_visited
    return rt_visited
ans=[0]*N
for i in range(N):
    Flag=[0]*N
    counted_r=count_r(i,Flag)
    Flag=[0]*N
    counted_t=count_t(i,Flag)
    ans[i]=sum(counted_r[j]*counted_t[j] for j in range(N))
text=str(ans[0])
for i in range(1,N):
    text+=" "+str(ans[i])
print(text)

Submission status: Runtime Error

Solution code:
N,K,L=map(int,input().split())
road=[[0]*N for i in range(N)]
train=[[0]*N for j in range(N)]

for i in range(K):
    p,q=map(int,input().split())
    road[p-1][q-1]=1
    road[q-1][p-1]=1
for j in range(L):
    r,s=map(int,input().split())
    train[r-1][s-1]=1
    train[s-1][r-1]=1


def count_r(node,visited):
    visited[node]=1
    ans=sum(visited)
    rt_visited=visited
    for i in range(N):
        if not visited[i] and road[node][i]:
            visited[i]=1
            rc_visited=count_r(i,visited)
            c_cnt=sum(rc_visited)
            if ans<c_cnt:
                ans=c_cnt
                rt_visited=rc_visited
    return rt_visited

def count_t(node,visited):
    visited[node]=1
    ans=sum(visited)
    rt_visited=visited
    for i in range(N):
        if not visited[i] and train[node][i]:
            visited[i]=1
            rc_visited=count_t(i,visited)
            c_cnt=sum(rc_visited)
            if ans<c_cnt:
                ans=c_cnt
                rt_visited=rc_visited
    return rt_visited
counted_r=[ 0 for j in range(N)]
counted_t=[ 0 for j in range(N)]
ans=[0]*N
for i in range(N):
    Flag=[0]*N
    counted_r[i]=count_r(i,Flag)
    Flag=[0]*N
    counted_t[i]=count_t(i,Flag)
    ans[i]=sum(counted_r[i][j]*counted_t[i][j] for j in range(N))
text=str(ans[0])
for i in range(1,N):
    text+=" "+str(ans[i])
print(text)

Submission status: Runtime Error

Solution code:
import copy

N, K, L = [int(i) for i in input().split()]
ROAD = [[] for i in range(N + 1)]
TRAIN = [[] for i in range(N + 1)]
path = set([])
ans = [[0] * 2 for i in range(N + 1)]
ans_num = [0] * (N + 1)
for i in range(K):
    a, b = [int(i) for i in input().split()]
    ROAD[a].append(b)
    ROAD[b].append(a)
for i in range(L):
    a, b = [int(i) for i in input().split()]
    TRAIN[a].append(b)
    TRAIN[b].append(a)


def check(now, n):
    for i in range(1, now):
        if now in ans[i][n]:
            return ans[i][n]
    return []


def solve(now, visited, road):  # 訪れたところを記録しておけば、後でその位置がスタートだった時に利用できる
    if now in visited:
        return path
    visited.append(now)
    path.add(now)
    if len(road[now]) is 0:
        return path
    for go in range(len(road[now])):
        solve(road[now][go], visited[:], road[:])
    return path


tes = []
for i in range(1, N + 1):
    tes = check(i, 0)
    if len(tes) is 0:
        path = set([])
        tmp = solve(i, [], ROAD[:])
        ans[i][0] = list(tmp)
    else:
        ans[i][0] = tes
        tmp = set(tes)
    tes = check(i, 1)
    if len(tes) is 0:
        path = set([])
        tmp2 = solve(i, [], TRAIN[:])
        ans[i][1] = list(tmp2)
    else:
        ans[i][1] = tes
        tmp2 = set(tes)
    ans_num[i] = copy.deepcopy(list(tmp & tmp2))

A = []
for i in range(1, len(ans_num)):
    A.append(len(ans_num[i]))
print(' '.join(map(str, A)))

Submission status: Runtime Error

Solution code:
import copy

N, K, L = [int(i) for i in input().split()]
ROAD = [[] for i in range(N + 1)]
TRAIN = [[] for i in range(N + 1)]
path = set([])
ans = [[0] * 2 for i in range(N+1)]
ans_num = [0]*(N+1)
for i in range(K):
    a, b = [int(i) for i in input().split()]
    ROAD[a].append(b)
    ROAD[b].append(a)
for i in range(L):
    a, b = [int(i) for i in input().split()]
    TRAIN[a].append(b)
    TRAIN[b].append(a)



def solve(now, visited, road):  # 訪れたところを記録しておけば、後でその位置がスタートだった時に利用できる
    if now in visited:
        return path
    visited.append(now)
    path.add(now)
    if len(road[now]) is 0:
        return path
    for go in range(len(road[now])):
        solve(road[now][go], visited[:], road[:])
    return path


for i in range(1, N+1):
    path = set([])
    tmp = solve(i, [], ROAD[:])
    ans[i][0] = list(tmp)
    path = set([])
    tmp2 = solve(i, [], TRAIN[:])
    ans[i][1] = list(tmp2)
    ans_num[i] = copy.deepcopy(list(tmp & tmp2))

A = []
for i in range(1,len(ans_num)):
    A.append(len(ans_num[i]))
print(' '.join(map(str,A)))

Submission status: Runtime Error

Solution code:
import collections

def solution():
	pArr = []
	qArr = []
	rArr = []
	sArr = []

	cities = []

	answer = []

	line = raw_input()

	n, k, l = line.split(' ')

	for i in range (n):
		cities.append(i)

	for i in range(k):
		line = raw_input()
		p, q = line.split(' ')
		pArr.append(p)
		qArr.append(q)

	for i in range(l):
		line = raw_input()
		r,s = line.split(' ')
		rArr.append(r)
		sArr.append(s)

	railways = {}
	roads = {}

	for i in range(k):
		roads[i] = [pArr[i], qArr[i]]

	for i in range(l):
		railways[i] = [rArr[i], sArr[i]]
	
	for i in range(n):
		print traverse(cities[i], cities, railways, roads)
	
def traverse(city, cities, railways, roads):
	q = collections.deque()
	visited = {}
	q.append(city)
	visited[city] = True

	numCities = 0

	while len(q) != 0:
		c = q.popleft()

		if c in railways and c not in visited:
			q.append(railways[c])
			visited[railways[c]] = True
			numCities+=1
		if c in roads and c not in visited:
			q.append(roads[c])	
			visited[roads[c]] = True
			numCities+=1
	return numCities
		

			
solution()

Submission status: Runtime Error

Solution code:
class Node():
	def __init__(self, value):
		self.value = value
		self.connect = []
		self.visited = False

	def getConnect(self):
		return self.connect

	def setConnect(self, connects):
		self.connect = connects

	def getConnectValues(self):
		res = []
		for node in self.connect:
			res.append(node.getValue())
		return res

	def getValue(self):
		return self.value

	def addConnect(self, connectNode):
		self.connect.append(connectNode)

	def addConnects(self, connectNodes):
		self.connect += connectNodes

	def visitAll(self):
		self.visited = True
		for i in range(len(self.connect)):
			if self.connect[i].visited:
				continue
			else:
				self.connect[i].visitAll()

def computeAllConnects(node, list1):
	node.visitAll()
	res = []
	for i in range(1,len(list1)):
		if list1[i].visited:
			res.append(list1[i])
	node.setConnect(res)
	refreshVisited(list1)

def refreshVisited(list1):
	for i in range(1,len(list1)):
		list1[i].visited = False

def computeDuplicate(list1, list2):
	res = []
	for i in list1:
		if i in list2:
			res.append(i)
	return res

line1 = input()
line1 = line1.split(" ")
numCities = int(line1[0])
numRoads = int(line1[1])
numRails = int(line1[2])

road = [0]
rail = [0]
res = [0]

for i in range(1, numCities+1):
	road.append(Node(i))
	rail.append(Node(i))

for i in range(numRoads):
	lineI = input().split(" ")
	city1 = road[int(lineI[0])]
	city2 = road[int(lineI[1])]
	city1.addConnect(city2)
	city2.addConnect(city1)

for i in range(numRails):
	lineI = input().split(" ")
	city1 = rail[int(lineI[0])]
	city2 = rail[int(lineI[1])]
	city1.addConnect(city2)
	city2.addConnect(city1)

for i in range(1, numCities+1):
	computeAllConnects(road[i], road)
	computeAllConnects(rail[i], rail)

for i in range(1,numCities+1):
	roadConnects = road[i].getConnectValues()
	railConnects = rail[i].getConnectValues()
	res.append(len(computeDuplicate(roadConnects, railConnects)))

res = res[1:]

for i in range(0,len(res)-1):
	print(res[i], end=" ")
print(res[len(res)-1])

Submission status: Runtime Error

Solution code:
import java.util.*;

public class Main
{
    public static void main(String... args){
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int l = sc.nextInt();
//        int n = 100000;
//        int k = 100000;
//        int l = 100000;
        List<Set<Integer>> road = new ArrayList<>();
        List<Set<Integer>> rail = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            road.add(new HashSet<>());
            rail.add(new HashSet<>());
        }
        for (int i = 0; i < k; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
//            int s = i + 1;
//            int t = (i + 2) % 100000 + 1;
            s--;
            t--;
            road.get(s).add(t);
            road.get(t).add(s);
        }
        for (int i = 0; i < l; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
//            int s = i + 1;
//            int t = (i + 1) % 100000 + 1;
            s--;
            t--;
            rail.get(s).add(t);
            rail.get(t).add(s);
        }

        Map<Integer, Set<Integer>> roadCon = new HashMap<>();
        Map<Integer, Set<Integer>> railCon = new HashMap<>();

        dfs(road, roadCon, n);
        dfs(rail, railCon, n);

        for (int i = 0; i < n; i++) {
            System.out.print(intersect(roadCon.get(i), railCon.get(i)));
            System.out.print(" ");
        }

    }

    public static int intersect(Set<Integer>s1, Set<Integer>s2){
        int total = 0;
        if (s1.size() < s2.size()) {
            for (int i : s1) {
                if (s2.contains(i)) {
                    total++;
                }
            }
        } else {
            for (int i : s2) {
                if (s1.contains(i)) {
                    total++;
                }
            }
        }
        return total;
    }

    public static void dfs(List<Set<Integer>> road, Map<Integer, Set<Integer>> con, int n){
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]){
                Stack<Integer> s = new Stack<>();
                s.push(i);
                Set<Integer> tocon = new HashSet<>();
                while (!s.empty()){
                    int t = s.pop();
                    tocon.add(t);
                    visited[t] = true;
                    for (int j : road.get(t)) {
                        if (!visited[j]){
                            s.push(j);
                        }
                    }
                }
                for (int j : tocon) {
                    con.put(j, tocon);
                }
            }
        }
    }

}

Submission status: Runtime Error

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))

    def is_same_set(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def union_set(self, x: int, y: int):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return

        self.parent[x] = y

    def find_root(self, x: int):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find_root(self.parent[x])
            return self.parent[x]


def dfs(n, used, edges, uf: UnionFind):
    used[n] = True
    for a in edges[n]:
        if not used[a]:
            uf.union_set(n, a)
            dfs(a, used, edges, uf)


def main():
    N, K, L = map(int, input().split())
    d1 = defaultdict(list)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        d1[p].append(q)
        d1[q].append(p)

    d2 = defaultdict(list)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        d2[r].append(s)
        d2[s].append(r)

    uf1 = UnionFind(N)
    used1 = [False] * N
    for n in range(N):
        if not used1[n]:
            dfs(n, used1, d1, uf1)

    uf2 = UnionFind(N)
    used2 = [False] * N
    for n in range(N):
        if not used2[n]:
            dfs(n, used2, d2, uf2)

    used3 = [False] * N
    ans = [0] * N
    for n1 in range(N):
        if used3[n1]:
            continue
        num = 1
        l = [n1]
        for n2 in range(n1 + 1, N):
            if not used3[n2]:
                if uf1.is_same_set(n1, n2) and uf2.is_same_set(n1, n2):
                    used3[n2] = True
                    l.append(n2)
                    num += 1
        for n in l:
            ans[n] = num

    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
same_roads = {}
same_rails = {}

max_road_id = -1
for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  if roads[p] < 0 and roads[q] < 0:
    max_road_id += 1
    roads[p] = max_road_id
    roads[q] = max_road_id
  elif roads[p] == roads[q]:
    continue
  elif roads[p] >= 0 and roads[q] < 0:
    roads[q] = roads[p]
  elif roads[q] < 0 and roads[q] >= 0:
    roads[p] = roads[q]
  else:
    same_roads[max(roads[p],roads[q])] = min(roads[p],roads[q]) 
distinct_roads = [i for i in range(max_road_id + 1)]
for road_id in range(max_road_id, -1, -1):
  if road_id in same_roads:
    distinct_roads[road_id] = same_roads[road_id]
 
max_rail_id = -1
for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  if rails[r] < 0 and rails[s] < 0:
    max_rail_id += 1
    rails[r] = max_rail_id
    rails[s] = max_rail_id
  elif rails[r] == rails[s]:
    continue
  elif rails[r] >= 0 and rails[s] < 0:
    rails[s] = rails[r]
  elif rails[r] < 0 and rails[s] >= 0:
    rails[r] = rails[s]
  else:
    same_rails[max(rails[r],rails[s])] = min(rails[r],rails[s])
distinct_rails = [i for i in range(max_rail_id + 1)]
for rail_id in range(max_rail_id, -1, -1):
  if rail_id in same_rails:
    distinct_rails[rail_id] = same_rails[rail_id]

combi_counts = {}
for i in range(N):
  road = roads[i]
  rail = rails[i]
  if road < 0 or rail < 0:
    continue
  if (road,rail) in combi_counts:
    combi_counts[(distinct_roads[road],distinct_rails[rail])] += 1
  else:
    combi_counts[(distinct_roads[road],distinct_rails[rail])] = 1

result = []
for i in range(N):
  road = roads[i]
  rail = rails[i]
  if road < 0 or rail < 0:
    result.append(1)
  else:
    result.append(combi_counts[(distinct_roads[road],distinct_rails[rail])])
print ' '.join(map(str, result))

Submission status: Runtime Error

Solution code:
from collections import Counter
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)
        a[q-1].append(p-1)
    b = list(range(n))
    for i in range(n):
        def g(j):
            if b[j] != j:
                return
            b[j] = i
            for k in a[j]:
                g(k)
        g(i)
    return b
a = f(k)
b = f(l)
c = Counter((a[i],b[i]) for i in range(n))
print(' '.join((str(c[a[i],b[i]]) for i in range(n))))

Submission status: Runtime Error

Solution code:
from collections import Counter
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)
        a[q-1].append(p-1)
    b = list(range(n))
    for i in range(n):
        def g(j):
            if b[j] != j:
                return
            b[j] = i
            for k in a[j]:
                g(k)
        g(i)
    return b
a = f(k)
b = f(l)
c = Counter((a[i],b[i]) for i in range(n))
print(' '.join((str(c[a[i],b[i]]) for i in range(n))))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n,k,l=map(int,input().split())
st=[] # streets
rr=[] # railroads

for _ in range(n):
    st.append([])
    rr.append([])

for _ in range(k):
    p,q = map(int,input().split())
    st[p-1].append(q-1)
    st[q-1].append(p-1)

for _ in range(l):
    p,q = map(int,input().split())
    rr[p-1].append(q-1)
    rr[q-1].append(p-1)

st_m=[0]*n
rr_m=[0]*n

def dfs(G,cur,M,m):
    M[cur]=m
    for next_cur in G[cur]:
        if M[next_cur]==0:
            dfs(G,next_cur,M,m)
m=1
for i in range(n):
    if st_m[i]==0:
        dfs(st,i,st_m,m)
        m+=1
m=1
for i in range(n):
    if rr_m[i]==0:
        dfs(rr,i,rr_m,m)
        m+=1

dd=defaultdict(int)
for pair in zip(st_m,rr_m):
    dd[pair]+=1
ans=[]
for pair in zip(st_m,rr_m):
    ans.append(str(dd[pair]))
print(' '.join(ans))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

int table[2][200000] = {{}, {}};

int uffind(int i, int x) {
  if (table[i][x] == -1) {
    return x;
  }
  return (table[i][x] = uffind(i, table[i][x]));
}

void ufunion(int i, int x, int y) {
  int s1 = uffind(i, x), s2 = uffind(i, y);
  if (s1 != s2) {
    table[i][s2] = s1;
  }
}

int main() {
  for (int i = 0; i < 200000; i++) {
    table[0][i] = table[1][i] = -1;
  }
  int n, k, l;
  cin >> n >> k >> l;
  for (int i = 0; i < k; i++) {
    int p, q;
    cin >> p >> q;
    p--; q--;
    ufunion(0, p, q);
  }
  for (int i = 0; i < l; i++) {
    int r, s;
    cin >> r >> s;
    r--; s--;
    ufunion(1, r, s);
  }
  map<int, vector<int> > d2;
  map<int, vector<int> > t2;
  for (int i = 0; i < n; i++) {
    int sd = uffind(0, i);
    decltype(d2)::iterator itd = d2.find(sd);
    if (itd == d2.end()) {
      vector<int> vd(1, i);
      d2.insert(make_pair(sd, vd));
    } else {
      itd->second.push_back(i);
    }
    int st = uffind(1, i);
    decltype(t2)::iterator itt = t2.find(st);
    if (itt == t2.end()) {
      vector<int> vt(1, i);
      t2.insert(make_pair(st, vt));
    } else {
      itt->second.push_back(i);
    }
  }
  for (int i = 0; i < n; i++) {
    decltype(d2)::iterator itd = d2.find(uffind(0, i));
    decltype(t2)::iterator itt = t2.find(uffind(1, i));
    vector<int> vd = itd->second;
    vector<int> vt = itt->second;
    vector<int> res(vd.size() + vt.size());
    sort(vd.begin(), vd.end());
    sort(vt.begin(), vt.end());
    vector<int>::iterator it = set_intersection(vd.begin(), vd.end(), vt.begin(), vt.end(), res.begin());
    res.resize(it - res.begin());
    cout << res.size();
    if (i != n - 1) {
      cout << ' ';
    }
  }
  cout << endl;
  return 0;
}