== include(page="template/taskheader" task_id="wildcards") ==

Poveste şi cerinţă...

Numim *pattern* un şir *nevid* format doar din caracterele $0$, $1$ şi $?$. Spunem că două patternuri $A$ şi $B$ de aceeaşi lungime *se potrivesc* dacă şi numai dacă caracterele $?$ pot fi înlocuite convenabil cu $0$ şi $1$ astfel încât cele două şiruri să devină identice. De exemplu, pentru $A = “110?1”$, $B = “1?001”, C = “??1?1”$, şirurile $A$ şi $B$ se potrivesc (se poate forma şirul $“11001”$ prin înlocuirea semnelor de întrebare cu valori),
dar şirurile $A$ şi $C$ nu se potrivesc.
 
Se dă un arbore (graf neorientat conex aciclic) cu $N$ noduri. Se cere să se atribuie fiecărui nod câte un şir format din caracterele $0$, $1$ şi $?$ (un pattern) astfel încât să se respecte următoarele proprietăţi:
 
* Toate patternurile să aibă aceeaşi lungime, care să fie cât mai mică (a se vedea rubrica *Punctare*).
* Pentru oricare două noduri distincte $u$ şi $v$, patternurile asociate acestora se potrivesc dacă şi numai dacă există muchia $(u, v)$ în arbore.
 

h2. Date de intrare

Fişierul de intrare $wildcards.in$ ...

Fişierul de intrare $wildcards.in$ va conţine pe prima linie numărul de noduri din arbore $N$. Pe următoarele $N - 1$ linii fişierul va conţine câte două numere $a$ şi $b$ cu semnificaţia că există o muchie între $a$ şi $b$.

h2. Date de ieşire

În fişierul de ieşire $wildcards.out$ ...

Fişierul de ieşire $wildcards.out$ va contine $N$ linii, pe linia $i$ aflandu-se patternul nodului $i$.
 
h2. Punctaj

h2. Restricţii

În concurs punctajul pe un subtask era minimul dintre scorurile obţinute la testele din subtaskul respectiv, dar datorită unor limitări tehnice, punctarea se va face in felul următor:
!problema/wildcards?punctare.png!

* $... ≤ ... ≤ ...$

table(scoring). |_. Subtask |_. Punctaj |_. Constrangeri |
| 1
| 6 puncte
| 2 ≤ N ≤ 100, prag{~inf~} = 100, prag{~sup~} = 100
||
| 2
| 9 puncte
| 2 ≤ N ≤ 10, prag{~inf~} = 100, prag{~sup~} = 100
||
| 3
| 5 puncte
| 2 ≤ N ≤ 10000, prag{~inf~} = 34, prag{~sup~} = 34, *arborele este un lant de $N$ noduri*
||
| 4
| 5 puncte
| 2 ≤ N ≤ 10000, prag{~inf~} = 34, prag{~sup~} = 34, *arborele este binar complet*
||
| 5
| 35 puncte
| 2 ≤ N ≤ 10, prag{~inf~} = 101, prag{~sup~} = 200
||
| 6
| 40 puncte
| 2 ≤ N ≤ 10, prag{~inf~} = 34, prag{~sup~} = 42
|

h2. Exemplu
table(example). |_. wildcards.in |_. wildcards.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|4
1 2
1 3
1 4
|???
000
0?1
11?
||
|3
1 2
2 3
|0
?
1
||
|5
1 2
1 3
3 4
3 5
|?00
000
1??
110
101
||
|2
2 1
|?
?
|

h3. Explicaţie

...

Aceasta este figura pentru primul, respectiv cel de-al treilea exemplu:
 
 
!problema/wildcards?arbore1.png!
!problema/wildcards?arbore2.png!
 

== include(page="template/taskfooter" task_id="wildcards") ==