In molte parti della Russia nevica durante l'inverno. Ci sono $N$ città in Russia, numerate da $0$ a $N-1$. Ci sono $N-1$ strade, numerate da $0$ a $N-2$. La strada $i$ ($0 \le i \le N-2$) collega due città distinte $A_i$ e $B_i$ ($0 \le A_i < B_i \le N-1$) in entrambe le direzioni. È possibile viaggiare tra qualsiasi coppia di città distinte in Russia passando attraverso una qualche sequenza di strade.

La condizione di innevamento di ciascuna strada cambia di giorno in giorno. In un dato giorno, ogni strada è o innevata o non innevata. La condizione di innevamento di una strada non cambia nel corso di una singola giornata.

Anya e Boris lavorano presso il Dipartimento dei Trasporti russo. Anya lavora nel dipartimento di gestione delle informazioni stradali e Boris lavora nel dipartimento che risponde alle domande dei cittadini. La domanda di un cittadino è: "Qual è il numero minimo di strade innevate che devo attraversare per viaggiare dalla capitale, la città 0, a una certa altra città?" Di solito Boris risponde ai cittadini dopo aver ricevuto una domanda e aver comunicato con Anya.

Recentemente, in Russia si sta tenendo una gara mondiale di programmazione della durata di $Q$ giorni. Durante la gara si prevede che le linee di comunicazione saranno congestionate, rendendo difficile per Anya e Boris comunicare direttamente. Pertanto, Anya e Boris hanno deciso di comunicare nel seguente modo:

• All'inizio di ogni giornata, Anya riceve le informazioni sulle strade innevate per quel giorno e invia dei dati a un server di inoltro (relay server).
• Quando Boris riceve una domanda da un cittadino, risponde comunicando con il server di inoltro.

Tuttavia, ci sono i seguenti vincoli sulla comunicazione tra Anya e Boris:

• La capacità del server di inoltro è $L = 1000$ bit. Anya può memorizzare al più $L$ bit di informazioni nel server di inoltro.
• I dati memorizzati nel server di inoltro vengono inizializzati tutti a 0 all'inizio di ogni giornata.
• Boris può leggere 1 bit specifico di informazione interagendo una volta con il server di inoltro.
• Per rispondere a una domanda, Boris può interagire con il server di inoltro al massimo 20 volte per domanda.

A te, conoscente del Direttore del Dipartimento dei Trasporti, è stato chiesto di ideare una strategia per Anya e Boris.

Scrivi un programma che implementi una strategia per Anya e Boris in grado di rispondere correttamente alle domande dei cittadini.

Dettagli di implementazione

È necessario sottoporre due file nello stesso linguaggio di programmazione.

Il primo file si chiama Anya.c o Anya.cpp. Questo file implementa la strategia di Anya e deve implementare le seguenti due funzioni. Il programma deve includere Anyalib.h.

• void InitAnya(int N, int A[], int B[]) Questa funzione viene chiamata esattamente una volta per ciascun caso di test.

  • L'argomento N rappresenta il numero di città.
  • Gli argomenti A[] e B[] sono array di lunghezza $N-1$, che rappresentano le informazioni sui collegamenti stradali. Gli elementi A[i] e B[i] ($0 \le i \le N-2$) sono interi che indicano che la strada $i$ collega le città A[i] e B[i] in entrambe le direzioni, soddisfacendo $0 \le A[i] < B[i] \le N-1$.

• void Anya(int C[]) Questa funzione viene chiamata $Q$ volte dopo la chiamata a InitAnya. Questa funzione corrisponde alla decisione di Anya sulla stringa di bit da memorizzare nel server di inoltro dopo che le informazioni sulle strade innevate sono state aggiornate all'inizio della giornata.

  • L'argomento C[] è un array di lunghezza $N-1$, che rappresenta le informazioni sulle strade innevate. L'elemento C[i] ($0 \le i \le N-2$) è un intero pari a 0 o 1, dove C[i] = 1 significa che la strada $i$ è innevata e C[i] = 0 significa che la strada $i$ non è innevata.

All'interno della funzione Anya, è possibile chiamare la seguente funzione:

• void Save(int place, int bit) Questa funzione rappresenta l'operazione con cui Anya salva un bit nel server di inoltro.

  • L'argomento place rappresenta la posizione in cui scrivere il bit. place deve essere un intero compreso tra $0$ e $L-1$ inclusi. Se viene specificato un valore al di fuori di questo intervallo, viene giudicato come Wrong Answer [1]. Inoltre, in ciascuna chiamata alla funzione Anya, non è possibile chiamare questa funzione con lo stesso argomento place più di una volta. Se viene chiamata due volte con lo stesso argomento, viene giudicato come Wrong Answer [2].
  • L'argomento bit è un intero che rappresenta il bit da scrivere, che deve essere 0 o 1. Se viene specificato qualsiasi altro valore, viene giudicato come Wrong Answer [3].

Dopo la chiamata a Save, il contenuto del place-esimo bit del server di inoltro diventa bit. Se una chiamata a Save viene giudicata come Wrong Answer, il programma termina in quel punto.

Immediatamente prima che venga chiamata la funzione Anya, i bit nel server di inoltro vengono sempre inizializzati tutti a 0. Cioè, al termine della funzione Anya, le posizioni in cui non è stata eseguita alcuna operazione di salvataggio tramite la funzione Save contengono 0.

Il secondo file si chiama Boris.c o Boris.cpp. Questo file implementa la strategia di Boris e deve implementare le seguenti due funzioni. Il programma deve includere Borislib.h.

• void InitBoris(int N, int A[], int B[]) Questa funzione viene chiamata esattamente una volta per ciascun caso di test.

  • L'argomento N rappresenta il numero di città.
  • Gli argomenti A[] e B[] sono array di lunghezza $N-1$, che rappresentano le informazioni sui collegamenti stradali. Gli elementi A[i] e B[i] ($0 \le i \le N-2$) sono interi che indicano che la strada $i$ collega le città A[i] e B[i] in entrambe le direzioni, soddisfacendo $0 \le A[i] < B[i] \le N-1$.

• int Boris(int city) Questa funzione viene chiamata diverse volte dopo la chiamata a InitBoris. Questa funzione corrisponde all'azione di Boris in risposta alla domanda di un cittadino.

  • L'argomento city rappresenta la domanda del cittadino. city è un intero compreso tra $1$ e $N-1$ inclusi. Ciò rappresenta il cittadino che chiede il numero minimo di strade innevate che deve attraversare per viaggiare dalla città 0 a city.
  • La funzione Boris deve restituire un intero compreso tra $0$ e $N-1$ inclusi, che è la risposta alla domanda del cittadino. Se viene restituito un intero al di fuori di questo intervallo, viene giudicato come Wrong Answer [4]. Se la risposta non è corretta, viene giudicato come Wrong Answer [7].

All'interno della funzione Boris, è possibile chiamare la seguente funzione:

• int Ask(int place) Questa funzione rappresenta l'operazione con cui Boris legge un bit dal server di inoltro.

  • L'argomento place rappresenta la posizione da cui leggere il bit. place deve essere un intero compreso tra $0$ e $L-1$ inclusi. Se viene specificato un valore al di fuori di questo intervallo, viene giudicato come Wrong Answer [5].

  Il valore restituito dalla funzione Ask è un intero che rappresenta il contenuto del place-esimo bit del server di inoltro, che è 0 o 1. Inoltre, la funzione Ask può essere chiamata al massimo 20 volte in ciascuna chiamata alla funzione Boris. Se viene chiamata più di 20 volte, viene giudicato come Wrong Answer [6].

Se una chiamata a Ask viene giudicata come Wrong Answer, il programma termina in quel punto.

Vincoli

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1 + \dots + D_Q \le 500$.
• È possibile viaggiare tra qualsiasi coppia di città distinte passando attraverso una qualche sequenza di strade.

Subtask

1. (15 punti) $N \le 20$.
2. (5 punti) $N \le 100$.
3. (35 punti) $A_i = i$ e $B_i = i + 1$ per tutti gli $0 \le i \le N-2$.
4. (45 punti) Nessun vincolo aggiuntivo.

Esempi

Input 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Output 1

1 0 2
2

Nota

L'esempio sopra mostra il flusso di interazione. La prima riga di input è $N=5$. Le successive 4 righe definiscono gli archi. La riga successiva è $Q=2$. Le righe seguenti descrivono le strade innevate e le query per ciascun giorno. L'output mostra le risposte fornite da Boris per le query di ciascun giorno.