daridolgova

08.02.2022 00:24 •  Информатика

E. ставки перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. каждая ставка имеет вид "таракан №a придет раньше, чем таракан №b". организаторы бегов решили выяснить, могут ли тараканы прийти в таком порядке, чтобы у каждого болельщика сыграла ровно одна ставка из двух (то есть чтобы ровно одно из двух утверждений каждого болельщика оказалось верным). считается, что никакие два таракана не могут прийти к финишу одновременно. формат входных данных в первой строке входного потока записаны два натуральных числа через пробел: число k, не превосходящее 10, — количество тараканов и число n, не превосходящее 100, — количество болельщиков. все тараканы пронумерованы числами от 1 до k. каждая из следующих n строк содержит 4 натуральных числа a, b, c, d, не превосходящих k, разделенных пробелами. они соответствуют ставкам болельщика "таракан №a придет раньше, чем таракан №b" и "таракан №c придет раньше, чем таракан №d". формат выходных данных если завершить бега так, чтобы у каждого из болельщиков сыграла ровно одна из двух ставок, можно, то следует вывести номера тараканов в том порядке, в котором они окажутся в итоговой таблице результатов (сначала номер таракана, пришедшего первым, затем номер таракана, пришедшего вторым и т. д.) в одну строку через пробел. если таких вариантов несколько, выведите любой из них. если требуемого результата добиться нельзя, выведите одно число 0. примеры входные данные выходные данные 3 2 2 1 2 3 1 2 3 2 3 2 1 3 4 1 2 1 3 1 2 3 1 1 2 2 3 1 2 3 2 0