Hello everybody! My name is Gerald Agapov. I study at Saratov State University. Today I present you the set of, I hope interesting, problems. Good luck to all!

And also a warm thanks RAD, MikeMirzayanov and the entire Codeforces team for the great system and this opportunity! (с) dolphinigle

Because I am printing only two type of answers :: "2" and "1 000000001"

I only wished it has a larger memory limit though.

It were like you said some time ago. Now it's better, because if you have an issue and can't come back home, then you don't need to unregister (this happened to me)

Because the rating system is flawd sorry.

I liked problems C and D. But I fear this round might have been too hard for the division2 participants.

Thanks a lot for the round :)

Isn't it unfair that if somebody read problems and couldn't submit any solution then that round will be unrated for him.

Big thanks to the author for the contest.

Nice problems too. :)

1. Try to find any cycle. If there are no cycles prints -1.

Because of definition of tournament graph. If A[i][j] = 0 then A[j][i] = 1 (i != j).

Here's my somewhat different approach:

outward set, and the other set asinward set.inward set, say, I, Iterate over all members ofoutward set, say, O. If an edge is present from I to O (in that direction), return the triple (I, O, X).outward setandinward set, separately.sorry, wrong branch

Could You explain more clearly point 3 ? If I iterate over all

Inward setand for every element inInwardI check all edges toOutwardI will definitely get |Inward| * |Onward|, so N^2, so the whole alogrithm will be working in N^3. I suppose point 3 should work in linear time, but I don't know how.I totally misread this part in the contest ! :( Sorry for that.

count[v] be the number of outcoming edges of the vertex v. Then number of incoming edges isn-count[v] - 1. Suppose we take two first vertices of the cycle, name themvandu. And there is the edgevuin the graph. Proposal: (count[u] ≥count[v]) then there existswsuch that there is the cyclev→u→w. Let's prove it: suppose we have a vertexw, that there is the edgesuwandwv, then we have a cycle. Let's look at the sets of incoming edges ofvand outcoming edges ofu, if they intersect, then there is suchw. Supposecount[u] ≥count[v] and suppose their sets of outcoming and incoming sets don't intersect. Then the cardinality of their union isn-count[v] - 1 +count[u]. This union doesn't containvandu. Son-count[v] - 1 +count[u] ≤n- 2,count[u] ≤count[v] - 1 andcount[u] <count[v], so there is contradiction.vu, such thatcount[u] ≥count[v]. Let's look at cycle, name their verticesv_{1},v_{2},v_{3}. As we supposedcount[v_{1}] >count[v_{2}] andcount[v_{2}] >count[v_{3}] andcount[v_{3}] >count[v_{1}], socount[v_{1}] >count[v_{1}], thats impossible.vu, and ifcount[u] ≥count[v], then find the third vertex of the cycle.Thanks for explaining .If I understood correctly , the two para's are respectively "if" and "only if" parts for proving

count[u] >= count[v]for existence of cycle ,right ?This is my opinion:

See the graph as a real tournament, every pairs of different teams plays exactly 1 match. We use an array

rank[], in which teams with lower rank always win teams with higher one.- Firstly,

rank[1] = 1.- Consider team

I.- Find the best team (smallest rank) that team

Iwins, call itW.- Find the worst team (highest rank) that team

Iloses, call itL.We easily observe that

rank[L]+1>=rank[W].If team

Wwins teamL, we have a cycleIwinsW,WwinsLandLwinsI.Otherwise

rank[I]=rank[L]+1, andrank[W→array end]+=1It works in O(n^2).

rank[]?initially rank[1] = 1 then rank[I] = rank[L] + 1 and rank[W->array end] += 1.

Are rank[] initially filled with 0's ?

If u know something about FFT(Fast Fourier Transform), it should be better to get in that. Here's my very complex solve, if u had better, plz tell me. : )

Probably because fgets is faster than cin.

EDIT: missing word.