Институтот за јавно здравје врши анализа на позитивните случаи на КОВИД-19, вклучувајќи ја секоја нивна средба со други лица. При анализа на контактите, за секое лице, тие ги означуваат нивните “опасни” средби (каде некое од двете лица не носело маска, на пример) и нивните “безбедни” средби (каде лицата носеле маски).

Досега, Институтот за јавно здравје знае за M лица, вкупно O опасни средби и S безбедни средби. Притоа, за секоја опасна средба помеѓу две лица Ai и Bi, тие имаат означено двонасочна врска помеѓу соодветните две лица Ai и Bi. Слично, за секоја безбедна средба помеѓу две лица Ci и Di, тие имаат означено двонасочна врска помеѓу соодветните две лица Ci и Di.

Сега, нив ги интересираат потенцијални опасни контакти кои не се откриени досега, па за едно лице X велиме дека тоа е “потенцијален опасен контакт” за лице Y доколку X<>Y, и се исполнети следните три услови:

    1. X и Y немаат означена опасна средба
    2. X и Y немаат означена безбедна средба
    3. Постои синџир од опасни средби X -> P1 -> P2 -> … -> P? -> Y, каде што имало опасна средба помеѓу X и P1, P1 и P2, …, P? и Y.

Напишете програма која за секој од М-те лица познати на Институтот за јавно здравје ќе го пресмета и отпечати бројот на потенцијални опасни контакти.

Влез

Во првиот ред е запишан еден цел број M (2 <= M <= 100 000), бројот на лица.

Во вториот ред е запишан еден цел број O (1 <= O <= 100 000), бројот на опасни средби. Во секој од наредните O редови е запишан по еден пар од броеви Ai и Bi (1 <= Ai, Bi <= M), кој означува дека постои откриена опасна средба помеѓу лицата Ai и Bi (притоа, важи Ai <> Bi, и сите дадени O парови означуваат различна средба).

Во следниот ред е запишан еден цел број S (1 <= S <= 100 000), бројот на безбедни средби. Во секој од наредните S редови е запишан по еден пар од броеви Ci и Di (1 <= Ci, Di <= M), кој означува дека постои откриена безбедна средба помеѓу лицата Ci и Di (притоа, важи Ci <> Di, и сите дадени S парови означуваат различна средба). Нема да постои пар кој што се појавува и како опасна и како безбедна средба.

Забелешка: Во тест случаи кои носат најмалку 15% од поените, бројот M ќе биде помал или еднаков на 7. Во други тест случаи кои носат најмалку 30% од поените, бројот M ќе биде помал или еднаков на 20.

Излез

За секој од M-те лица познати на Институтот за јавно здравје, во посебен ред, отпечатете го бројот на потенцијални опасни контакти (во првиот ред за лицето 1, во вториот ред за лицето 2, итн...)

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5
4
2 3
3 4
1 2
1 3
2
1 4
1 5

излез
0
1
0
1
0

влез
7
5
1 2
2 3
4 5
5 3
6 7
1
6 5

излез
3
2
2
3
2
0
0

Објаснување за првиот тест пример: Веќе постојат 4 откриени опасни средби помеѓу лицата 1 и 2, 1 и 3, 2 и 3, 3 и 4. Слично, постојат 2 проверени безбедни средби помеѓу лицата 1 и 4, и 1 и 5.

Потенцијален опасен контакт постои помеѓу лицата 2 и 4 (бидејќи постои синџир од опасни средби помеѓу 2 и 3, и 3 и 4), а таквиот контакт 2->4 не е досега означен ниту како опасна средба ниту како безбедна средба.