---
# System prepended metadata

title: Kriminalist

---

# Kriminalist

Kriminalist se sklanja nad poročilo, ki vsebuje dva različna opisa morda iste mafijske družine. Vsak član družine je označen z dvema velikima črkama (npr. AB za Andreja Barabo), vendar pa se v drugem opisu lahko za isto osebo uporablja drugačen par črk. Na primer, isti Andrej Baraba bi lahko bil v drugem opisu označen kot BJ (Brezmejno Junaški). V obeh opisih pa zanesljivo velja, da so različni člani predstavljeni z različnimi pari črk. Oba opisa podajata hierarhična razmerja med člani družine (npr. član AB je nadrejen članu CD). Znano je, da ima vsak član družine lahko kvečjemu dva podrejena.

Če se opisa razlikujeta samo po oznakah posameznih članov, število članov in hierarhična razmerja med člani pa sta v obeh opisih enaka, potem kriminalist sklene, da gre za isto mafijsko družino. V nasprotnem primeru pa ne more reči ničesar, saj opisa nista nujno popolna.

Napiši program, ki prebere število $n$ in $n$ parov opisov mafijskih družin in za vsak par izpiše 1, če se opisa po kriminalistovih kriterijih nanašata na isto mafijsko družino, in 0, če to ne drži.

## Vhod

Prva vrstica vsebuje število parov opisov ($n \in [1, 10]$), naslednjih $n$ vrstic pa posamezne pare opisov. Vsaka od teh vrstic je sestavljena iz dveh nizov dolžine $L$, ločenih s presledkom. Vsak niz je sestavljen iz samih velikih črk angleške abecede.  Po dve zaporedni črki predstavljata člana družine, po dva zaporedna para pa hierarhično razmerje (član, ki ga predstavlja prvi par, je nadrejen članu, ki ga predstavlja drugi par).  Dolžina niza je zato deljiva s 4.  Na primer, niz ABCDCDEFCDGH beremo kot (AB, CD), (CD, EF), (CD, GH), kar pomeni, da je član AB nadrejen članu CD, član CD pa članoma EF in GH.

## Izhod

Izpiši $n$ vrstic.  V $i$-ti vrstici (za $i \in \{1, \ldots, n\}$) naj bo zapisano število 1, če lahko kriminalist sklene, da se opisa v $i$-tem paru nanašata na isto mafijsko družino, in 0, če tega ne more storiti.

## Omejitve vhoda

* (30 točk) $L \in [4, 4 \cdot 6]$.
* (30 točk) $L \in [4, 4 \cdot 64]$.
* (40 točk) $L \in [4, 4 \cdot 26^2]$.

## Primer

### Vhod

```
2
ABMKABST BJABBJUJ
JCTRJCPS SWRLFDSW
```

### Izhod

```
1
0
```

### Obrazložitev primera

Pri prvem paru lahko člane iz prvega opisa in člane iz drugega opisa povežemo s preslikavo AB $\mapsto$ BJ, MK $\mapsto$ AB, ST $\mapsto$ UJ (ali pa s preslikavo AB $\mapsto$ BJ, MK $\mapsto$ UJ, ST $\mapsto$ AB), pri drugem paru pa članov v prvem opisu ni mogoče povezati s člani v drugem opisu.
