h2. Restricţii
* $1 ≤ N ≤ 100 000$

* Se garanteaza ca intotdeauna exista o asezare posibila astfel incat sa se respecte restrictiile piticilor.

* Se garanteaza ca intotdeauna exista o asezare posibila astfel incat sa se respecte restrictiile celor $N$ pitici.

* Spunem că un drum A=(a ~1~,a ~2~,..,a ~N~) este mai mic lexicografic decât un drum B=(b ~1~, b ~2~,..,b ~N~) dacă există o poziţie p astfel încât x ~p~ < y ~p~ şi x ~1~ = y ~1~, x ~2~ = y ~2~,..., x ~p-1~ = y ~p-1~.
h2. Exemplu