== 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$ si $b$ cu semnificatia ca exista o muchie intre $a$ si $b$

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

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

| 2 ≤ N ≤ 10
prag_inf = 100
prag_sup = 100

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