Obeleži sve kategorije koje odgovaraju problemu

Повезан граф који садржи $n$ чворова и $n-1$ грана се назива дрво. Сваки чвор дрвета може бити његов корен. Напиши програм који за дато дрво и дати корен одређује смер свих грана у том коренском дрвету.

Улаз

Са стандардног улаза се уноси број чворова $n$ ($1 \leq n \leq 10^5$), а затим и опис $n-1$ грана дрвета. Свака грана је одређена бројевима полазног и завршног чвора (цели бројеви између $0$ и $n-1$), при чему су они задати у произвољном редоследу. У последњем реду се налази редни број корена (број између $0$ и $n-1$).

Излаз

На стандардни излаз треба исписати гране резултујућег коренског дрвета, при чему свака грана треба да буде оријентисана у смеру од корена ка листовима. Низ свих грана (парова бројева) треба да буде лексикографски сортиран (гране се пореде прво по првом, а затим по другом чвору).

Пример 1

Улаз

5
1 0
2 4
3 4
4 1
4

Излаз

1 0
4 1
4 2
4 3

Пример 2

Улаз

5
1 0
2 4
3 4
4 1
2

Излаз

1 0
2 4
4 1
4 3

Објашњење