Как гласят старые малоярославские легенды, где-то далеко-далеко, где сборная России когда-то готовилась к международной олимпиаде, в одной из общеобразовательных школ живёт Граф. Ориентированность Графа, как следует из легенд, меняется от дня ко дню вместе с количеством вершин и ребер, что позволяет Графине и её отражению не скучать и играть во множество игр на Графе.
Вот уже многие дни Граф обрёл постоянную ориентированность; однако в последнее время Граф часто стал бывать раздражительным и колючим, и для Графини настали нелёгкие дни. Чтобы хоть как-то облегчить себе жизнь, Графиня решила написать программу, которая по текущему состоянию, то есть набору вершин и рёбер, сообщит Графине, является ли граф колючим. По опыту прошлых дней, Графиня заключила, что Граф является колючим, если и только если через любое его ребро проходит не более чем один простой цикл.
Напомним, что последовательность ребер
(
u
1
,
u
2
)
,
(
u
2
,
u
3
)
, ...,
(
u
k
- 1
,
u
k
)
,
(
u
k
,
u
1
)
является простым циклом, если вершины
u
1
,
u
2
, ...,
u
k
попарно различны. Простой цикл проходит через ребро
e
, если ребро
e
содержится в последовательности ребер цикла.
Петлёй в графе называется ребро
(
u
,
v
)
, т.ч.
u
=
v
.
Рёбра
(
u
1
,
v
1
)
и
(
u
2
,
v
2
)
называются кратными, если
u
1
=
u
2
и
v
1
=
v
2
.
Помогите Графине понять, является ли её Граф, являющийся
ориентированным
графом без петель и кратных ребер, колючим или нет.