SNS має \(N\) користувачів – \(User1\), \(User\_2\), ..., \(User\_N\). Між цими \(N\) користувачами існують певні стосунки – дружні стосунки з \(М\) і блокування \(K\) користувачів. Для кожного \(i = 1, 2, \cdots, M\) існує двостороння дружба між \(User\_A\_i\) і \(User\_B\_i\). Для кожного \(i = 1, 2, \cdots, K\) існує двонаправлене блокування між \(User\_C\_i\) і \(User\_D\_i\) ​.

Ми визначаємо \(User\_a\) як кандидата в друзі для \(User\_b\), коли виконуються всі наступні чотири умови:

• \(a \neq b\).

• Між \(User\_a\) та \(User\_b\) немає дружби.

• Між \(User\_a\) і \(User\_b\) немає блокування.

• Існує послідовність \(c\_0, c\_1, c\_2, \cdots, c\_L\), що складається з цілих чисел від 1 до \(N\) (включно), таких що \(c\_0 = a\), \(c\_L = b\), і існує дружба між \(User\_c\_i\) і \(User\_c\_{i + 1}\) ​ для кожного \(i = 0, 1, \cdots, L - 1\).

Скільки є кандидатів у друзі для кожного користувача \(i = 1, 2, ... N\)?

Формат вхідних даних

Перший рядок містить цілі числа \(N, M, K\) (\(2 \le N \le 10^5\), \(0 \le M,K \le 10^5\)).

Наступні  \(M\) рядків містять цілі числа \(A\_i, B\_i\) (\(1 \le A\_i, B\_i \le N\), \(A\_i \neq B\_i\))

Наступні  \(K\) рядків містять цілі числа \(C\_i, D\_i\) (\(1 \le C\_i, D\_i \le N\), \(C\_i \neq D\_i\))

Ще обмеження:

\((A\_i ​,B\_i ​) \neq (A\_j ,B\_j)\) \((i \neq j)\)

\((A\_i, B\_i) \neq (B\_j, A\_j)\)

\((C\_i, D\_i) \neq (C\_j, D\_j)\) \((i \neq j)\)

\((C\_i, D\_i) \neq (D\_j, C\_j)\)

\((A\_i, B\_i) \neq (C\_j, D\_j)\)

\((A\_i, B\_i) \neq (D\_j, C\_j)\)

Формат вихідних даних

У вихідний потік виведіть відповіді по порядку, з пробілом між ними.

Примітка

До прикладу 1:

Існує дружба між \(User\_2\) і \(User\_3\), а також між \(User\_3\) і \(User\_4\). Крім того, немає дружби або блокування між \(User\_2\) і \(User\_4\).

Таким чином, \(User\_4\) є кандидатом у друзі для \(User\_2\). Однак жоден \(User\_1\) або \(User\_3\) не є кандидат у друзі для \(User\_2\), тож у \(User\_2\) є один кандидат у друзі.

Приклад вхідних даних

4 4 1
2 1
1 3
3 2
3 4
4 1

Приклад вихідних даних

0 1 0 1

Приклад вхідних даних

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Приклад вихідних даних

0 0 0 0 0

Приклад вхідних даних

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Приклад вихідних даних

1 3 5 4 3 3 3 3 1 0