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

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.

Numim *pattern* un sir *nevid* format doar din caracterele $0$, $1$ si $?$. Spunem că două patternuri $A$ si $B$ de aceeasi lungime *se potrivesc* daca si numai daca caracterele $?$ pot fi ı̂nlocuite convenabil cu $0$ si $1$ astfel incat cele două siruri să devină identice. De exemplu, pentru $A = “110?1”$, $B = “1?001”, C = “??1?1”$, sirurile $A$ si $B$ se potrivesc (se poate forma sirul $“11001”$ prin inlocuirea semnelor de intrebare cu valori),
dar sirurile $A$ si $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:

Se da un arbore (graf neorientat conex aciclic) cu $N$ noduri. Se cere să se atribuie fiecărui nod cate un sir format din caracterele $0$, $1$ si $?$ (un pattern) astfel incat să se respecte următoarele proprietati:

* 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.

 * Toate patternurile sa aiba aceeasi lungime, care să fie cat mai mica (a se vedea rubrica *Punctare*).
 * Pentru oricare două noduri distincte $u$ si $v$, patternurile asociate acestora se potrivesc dacă si numai dacă există muchia $(u, v)$ ı̂n arbore.

h2. Date de intrare

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$.

Fisierul de intrare $wildcards.in$ va contine pe prima linie numarul de noduri din arbore $N$. Pe urmatoarele $N - 1$ linii fisierul va contine cate doua numere $a_i$ si $b_i$ cu semnificatia ca exista o muchie intre $a_i$ si $b_i$

h2. Date de ieşire

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

Fisierul de iesire $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 |

|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
|?
?
|

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

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") ==