Problem #162

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 lista. 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 \(T_i\) (1≤i≤Q)

Cerinţă

Scrieţi un program care să determine pentru fiecare moment de timp \(T_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 \(L_k\), reprezentând numărul de noduri adiacente cu nodul k, urmat de \(L_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 \(T_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 \(T_i\).

şi precizări

  • \(M = L_1 + L_2 +...+L_N\)
  • 1 ≤ N, M, Q ≤ 50
  • \(1 ≤ L_k ≤ M\), 1≤k≤N
  • \(1 ≤ 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, \(1 ≤ 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.

General info

Uploader: liviu

Author: Emilian Miron

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

Submissions