albinuta

Time limit: 0.03s
Memory limit: 64MB
Input: albinuta.in
Output: albinuta.out

Albinuţa D are N flori preferate şi un mod aparte de a le culege polenul. Aceasta şi-a întocmit o hartă a florilor sub forma unui graf orientat cu N noduri şi M muchii, în care florile sunt nodurile grafului şi sunt numerotate cu 1,2,...,N. Pentru fiecare nod se cunoaşte lista de adiacenţă, ordonată conform preferinţelor albinuţei.

Traseul parcurs de albinuţă pentru culegerea polenului, porneşte din nodul cu numărul 1, la momentul de timp T=1. La fiecare moment de timp T albinuţa alege al T-lea nod din lista de adiacenţă, numărând circular T poziţii, începând cu primul nod din listă. Ea va ajunge la momentul T+1 în nodul astfel ales. De exemplu, dacă la momentul de timp T=12 lista de adiacenţă a nodului curent, ordonată conform preferinţelor albinuţei, este: 1 6 2 9 5, atunci la momentul T=13 albinuţa va ajunge în nodul 6.

Un apicultor a descoperit harta folosită de albinuţă şi se întreabă în ce floare se va afla aceasta la anumite momente de timp TiT_i (1≤i≤Q)

Cerinţă

Scrieţi un program care să determine pentru fiecare moment de timp TiT_i dat, floarea pe care se va afla albinuţa.

Date de intrare

Fişierul de intrare albinuta.in va conţine pe prima linie două numere naturale naturale N şi Q, separate printr-un singur spaţiu. Fiecare linie k, dintre următoarele N, conţine numărul natural LkL_k, reprezentând numărul de noduri adiacente cu nodul k, urmat de LkL_k numere naturale reprezentând lista de adiacenţă a acestuia, ordonată conform preferinţelor albinuţei. Numerele conţinute de cele N linii sunt separate prin câte un spaţiu. Următoarele Q linii vor conţine, în ordine, numerele T1,T2,...,TQT_1, T_2,... ,T_Q, câte unul pe linie.

Date de ieşire

Fişierul de ieşire albinuta.out va conţine Q linii.
Pe linia i se va scrie numărul nodului în care se va afla albinuţa la momentul de timp TiT_i.

Restricții şi precizări

  • M=L1+L2+...+LNM = L_1 + L_2 +...+L_N
  • 1 ≤ N, M, Q ≤ 50
  • 1LkM1 ≤ L_k ≤ M, 1≤k≤N
  • 1Ti1091 ≤ T_i ≤ 10^9, 1≤i≤Q
  • Într-o listă de adiacenţă, un nod poate apărea de mai multe ori.
  • Un nod poate apărea în lista lui de adiacenţă
  • Pentru 30% din teste, 1Ti1061 ≤ T_i ≤ 10^6

Exemplu

albinuta.in

6 5
2 2 1
2 1 3
3 4 5 6
1 5
1 6
1 1
1
2
3
4
5

albinuta.out

1
2
3
6
1

Explicație

Albinuţa va urma traseul: 1 2 3 6 1 la momentele de timp 1,2,3,4,5.

Problem info

ID: 162

Editor: liviu

Author:

Source: ONI 2008 XI-XII: Ziua 1 Problema 1

Tags:

ONI 2008 XI-XII

Log in or sign up to be able to send submissions!