Liars

YOU are a LIAR!!!!

Recent Zoli a descoperit un nou cartier în orașul Târgu Mureș. În acest cartier există $N$ oameni numerotați de la $1$ la $N$, fiecare om aflându-se într-o casă pe care ne-o putem imagina ca pe un nod într-un arbore (un graf neorientat conex cu $N$ noduri si $N - 1$ muchii). Muchiile grafului reprezintă relațiile de vecinătate între acești oameni (o muchie de la un nod $a$ la un nod $b$ semnifică faptul că omul $a$ este vecin cu omul $b$).

Dorind să se mute, Zoli a început să se intereseze de oamenii din acest cartier și de caracterul lor moral. El a aflat că în acest cartier există $2$ tipuri de oameni: sinceri și mincinoși. Oamenii sinceri sunt genul de oameni pe care orice i-ai întreba răspund doar cu adevărul (de exemplu dacă întrebi un olimpic la info care e sincer: "Salut boss, câte cifre există în baza 2?" o să răspundă "$10$"). În schimb, mincinoșii sunt genul de oameni pe care orice i-ai întreba, o să răspundă doar cu o minciună (de exemplu dacă întrebi un Tamio la info care e mincinos "Salut Tamio, câți bani faci făcând cercetare?", o să răspundă "Sunt milionar boss, eu îmi cumpăr doar ciocolată Poiana săracule!").

Ca să determine cine e mincinos și cine nu, Zoli a întrebat fiecare om $i$ din acest cartier "Câți vecini ai care sunt mincinoși?", iar fiecare om a răspuns cu o valoare $r_i$. Apoi, Zoli a dedus o configurație $C$ unde $C_i$ are valoarea $1$ dacă Zoli a dedus că omul $i$ este sincer, respectiv $0$ dacă a dedus că $i$ este mincinos. Configurația construită de Zoli nu se auto-contrazice: dacă $t_i$ este numărul de vecini $v$ ai omului $i$ pentru care $C_v$ este $0$, atunci dacă $C_i$ este $1$ atunci $r_i = t_i$, iar dacă $C_i$ este $0$ atunci $r_i \neq t_i$, pentru orice $1 \leq i \leq N$.

Cerință

Determinați numărul total de configurații distincte pe care le poate deduce Zoli din răspunsurile date de oamenii din cartier, precum și o configurație individuală pe care o poate deduce Zoli. Deoarece numărul de configurații poate fi foarte mare, trebuie să-l afișați modulo $666013$.

Date de intrare

Fișierul de intrare liars.in conține pe prima linie un număr natural $N$, reprezentând numărul de oameni din cartier. Pe a doua linie se găsesc $N$ numere naturale reprezentând răspunsurile oamenilor la întrebarea lui Zoli (al $i$-lea element de pe această linie este $r_i$). Următoarele $N - 1$ linii conțin fiecare câte două numere naturale $a$ și $b$, indicând faptul că omul $a$ și omul $b$ sunt vecini.

Date de ieșire

Fișierul de ieșire liars.out va conține pe prima linie un număr natural reprezentând numărul de configurații distincte pe care le poate deduce Zoli. Pe a doua linie va conține $N$ valori binare reprezentând o configurație posibilă pentru cei $N$ oameni. A $i$-a valoare este $0$ dacă Zoli a dedus că omul cu indicele $i$ este mincinos, respectiv $1$ dacă Zoli a dedus că omul cu indicele $i$ este sincer. Se garantează că mereu există cel puțin o configurație posibilă. Dacă există mai multe soluții posibile, se poate afișa oricare.

Restricții și precizări

• $4 \leq N \leq 5 \ 000$;
• $0 \leq r_i \leq t_i$;
• Două configurații $A$ și $B$ se consideră distincte dacă există o poziție $i$, $1 \leq i \leq N$, pentru care $A_i \neq B_i$.
• Pentru rezolvarea primei cerințe (numărul total de configurații distincte) se acordă $60\%$ din punctaj.
• Pentru rezolvarea celei de-a doua cerințe (reconstituirea unei soluții) se acordă $40\%$ din punctaj.
• Se garantează că pe cel puțin $1$ test, numărul total de soluții depășește modulo $666 \ 013$.

Exemplu

liars.in

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

liars.out

2
1 1 0 0 0 1 1

Explicație

Sunt $2$ configurații în total pe care le poate deduce Zoli: cea din exemplu este una din ele, cealaltă fiind 0 1 1 0 1 1 0.

Pentru soluția din exemplu explicația este următoarea:

• Nodul $1$ este vecin cu nodurile $2$ (sincer) și $3$ (mincinos), deci răspunsul corect la întrebare este $1$. Prin urmare, nodul $1$ este sincer deoarece a răspuns cu $1$.
• Nodul $2$ este vecin cu nodurile $1$ (sincer), $4$ (mincinos), $5$ (mincinos), $6$ (sincer), deci răspunsul pentru nodul $2$ este $2$. Prin urmare, nodul $2$ este sincer deoarece a răspuns cu $2$.
• Nodul $3$ este vecin doar cu nodul $2$ care este sincer, deci răspunsul la întrebare este $0$ (sunt $0$ mincinoși vecini cu el). Deoarece a răspuns cu $1$, nodul $3$ e mincinos.
• Nodul $4$ este vecin cu $2$. Asemănător cu nodul $3$, este mincinos.
• Nodul $5$ este vecin cu nodul $2$ și $7$ care sunt amândoi sinceri. Deoarece răspunsul este $0$ și a răspuns cu $1$, nodul $5$ e mincinos.
• Nodul $6$ e vecin cu $2$, deci $6$ e sincer pentru că a răspuns că sunt $0$ mincinoși vecini.
• Nodul $7$ este vecin cu $5$ care este mincinos. Răspunsul fiind $1$, nodul $7$ e sincer pentru că a răspuns cu $1$.