Задачи за тренинг

Задача 9а.
Напишете програма за обхождане на граф в ширина (BFS(1)).

Вход:
На входа се задава най-напред броя на дъгите на ориентиран граф, а после списък от тези дъги.Списъкът се състои от не повече от 1000 дъги, зададени с двойки номера на върхове - начало, край. Върховете на графа са номерирани с последователни цели положителни числа, започвайки от 1.
.
Изход:
Отпечатва се списък (редица) от върховете на графа, получени при обхождането му в ширина. Първият член на редицата трябва да бъде 1.

Пример:
3
1 2
2 3
1 4

Решение на примера:
1 2 4 3

Задача 9b.
Обхождане на граф в дълбочина (DFS(1)).

Вход:
На входа се задава най-напред броя на дъгите на ориентиран граф, а после списък от тези дъги.Списъкът се състои от не повече от 1000 дъги, зададени с двойки номера на върхове - начало, край. Върховете на графа са номерирани с последователни цели положителни числа, започвайки от 1.
.
Изход:
Отпечатва се списък (редица) от върховете на графа, получени при обхождането му в дълбочина. Първият член на редицата трябва да бъде 1.

Пример:
3
1 2
2 3
1 4

Решение на примера:
1 2 3 4

---