### Keshi's blog

By Keshi, 9 days ago,

Hints
Solution
Implementation

### 1610B - Kalindrome Array

Idea: -zeus-, Keshi, Preparation: AmShZ, Keshi

Hint
Solution
Implementation

### 1610C - Keshi Is Throwing a Party

Idea: Keshi, Preparation: Keshi

Hints
Solution
Implementation

Hints
Solution
Implementation

### 1610E - AmShZ and G.O.A.T.

Idea: AmShZ, Preparation: AmShZ

Hints
Solution
Implementation

### 1610F - Mashtali: a Space Oddysey

Idea: AliShahali1382, Preparation: AliShahali1382

Hint
Solution
Implementation

### 1610G - AmShZ Wins a Bet

Idea: AmShZ, Keshi, Preparation: AmShZ, Keshi, alireza_kaviani, AliShahali1382

Hints
Solution
Implementation

### 1610H - Squid Game

Idea: Tet, AliShahali1382, Preparation: AliShahali1382

Solution
Implementation

### 1610I - Mashtali vs AtCoder

Idea: AliShahali1382, Preparation: AliShahali1382

Solution
Implementation

• +170

 » 9 days ago, # |   +87 errorgorn cluck cluck cluck!
•  » » 9 days ago, # ^ | ← Rev. 3 →   +49 lol in all seriousness, no hard feeling about it. as a fellow problemsetter i also understand how hard it is to create strong pretets for problems because theres no way you can kill every possible weird thing people doi still remember in RAIF round there was the A had some condition like if (a==0 || b==0) and someone wrote if (a*b==0). Theres no way anyone will be able to predict that lolhonestly, i enjoyed this contest. having FGHI to jump around and finally solving G was really fun, thanks for setting this contest :)update: now we are both stupid chicken
•  » » » 9 days ago, # ^ |   +29 shit! what a stupid hack test
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   +28 You should see this too...In fact this thing TLEs on n=40 locally most of the times but cf reruns TLE submissions so I had to make n larger.K*re khar
 » 9 days ago, # |   +54 Btw just saying, the story in D was about the fact that we didn't have D $7$ days before the contest, because of the testers' feedback and also because the fact that I didn't solve C and D until about then, I decided to add D to fix the gap, it wasn't perfect however. Hopefully made the round better.
•  » » 9 days ago, # ^ |   +8 It kinda fixed the gap according to the numbers, and imo it is a decent problem. Won't ask for more from problem D in a div 1+2. P/S: It indeed made the round better.
•  » » » 9 days ago, # ^ |   +23 Thanks for your feedback. Makes me happy.
 » 9 days ago, # |   +94 Just a little suggestion: we should use $\geq$ and $\leq$ instead of $>=$ and $<=$ to make the editorial more pleasant to read.
•  » » 9 days ago, # ^ |   +25 Thanks!
 » 9 days ago, # |   +12 In problem I, am I the only person who actually solved the AtCoder problem in contest without looking at it?
 » 9 days ago, # |   -9 Lol! Testcases in ques.3 were pretty dumb..
 » 9 days ago, # |   +22 I think hint 3 from problem D is missing the sum symbol on the RHS.
•  » » 9 days ago, # ^ |   +10 Thanks!
 » 9 days ago, # |   +1 136659229 Can anyone tell me what is wrong in this code of B (Kalindrome Array). All similar codes got AC.
•  » » 9 days ago, # ^ |   +1 Integer's cache so that your '==' could be wrong.use int is ok.
•  » » » 9 days ago, # ^ |   0 Thanks, It solved my problem. But I never faced such type of problem with Integer before. What was the reason now?
•  » » » » 9 days ago, # ^ |   +5 The reason is simple you can't compare two objects with ==, cause it checks their references equality, instead you have to use the equals method.
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   +3 Integer will cache value between -127 to 128, and you can use '==' within this scope.if beyond this scope you should use 'equals' instead of '=='.For more details, you can see the source code of Integer.
•  » » » » 9 days ago, # ^ |   0 The reason is not coding in IDEA or ignoring IDEA's warning about objects comparison
 » 9 days ago, # |   +2 For problem C if the constraints supported O(N*N),then would DP work?
•  » » 9 days ago, # ^ |   0 Yes, we can do something like this. dp(len) denotes if the length of the sequence is len, then what is the maximum count of right_most elements that we can add to this sequence. And for each i, with dp(len) we can update dp(len+1) if dp(len) > 0.
•  » » » 9 days ago, # ^ |   0 I don't think 1-d DP will work, solely because the value of b[i]'s can differ and can produce different output, so I was asking about a solution based on dp[n][b[i]]!
 » 9 days ago, # | ← Rev. 5 →   -17 vscode txdy
 » 9 days ago, # |   +4 I cant understand D's explaining gcd(c1,c2,…,ck)=g s=∑ ci(ci−1) / 2 i= (1...k) when g is odd s % g == 0 && ci / 2 % g == 0 why how to explain c1 = 3,c2 = 9
•  » » 9 days ago, # ^ |   0 I guess it should have been, "If g is odd ci(ci-1) % (2g) == 0" Second para of This Comment might help
•  » » 9 days ago, # ^ |   +8 Me neither. Neither I understand what is "x" in x1c1+x2c2+…+xkck. I would understand it if the equation would be (x1c1 + c1/2) + (x2c2 + c2/2) + ... + (xkck + ck/2). For example if c1 would be 4, we can get sums like 2, 6, 10, ..., no 4, 8, 12, ...; or is "x" supposed not to be integer?Another point:∑i=1kxici=−sum is it supposed to be ∑i=1kxici=−s or what is "sum"?Btw sorry for formatting, but I don't know how it works on CF
 » 9 days ago, # |   +1 How is the below solution wrong for problem B? I am not able to figure out the test case.136636817
•  » » 9 days ago, # ^ |   +1 136659229 Same happened with me. Whereas all similar codes got AC.
•  » » 9 days ago, # ^ |   +1 Same, Got WA on 3414th token. Works with primitive type. OR, using Integer.equal(Integer) when comparing elements from list of Integer wrapper class also works. Not sure why!
•  » » » 9 days ago, # ^ |   0 Yeah exactly.
•  » » 9 days ago, # ^ | ← Rev. 3 →   +1 You might get WA on this test:51 3 2 4 1Edit: the result is correct, my bad
 » 9 days ago, # |   0 Can someone pls explain the even case in problem D ?
 » 9 days ago, # |   +5 Can anyone E in detail? I am not able to understand hint 1 properly.
•  » » 8 days ago, # ^ |   0 We know that an array is bad if it has a terrible subsequence. If the length of our terrible subsequence is bigger than 3, then we can remove some elements and it will remain terrible. So the array of three elements is terrible of a[1] < AVG < a[2]. If a[1] != a[2], then a[1] always smaller then AVG. So now we need to check AVG < a[2] -> (a[1] + a[2] + a[3]) / 3 < a[2] -> a[1] + a[2] + a[3] < 3 * a[2] -> a[1] + a[3] < 2 * a[2] -> a[3] — a[2] < a[2] — a[1]. If in our array exists three elements (i < j < k) such that a[k] — a[j] < a[j] — a[i] then our array is bad. If we take the first element as i, our a[j] — a[i] will be maximized, and if we take two consecutive j and k then our a[k] — a[j] will be minimized. We can only check all consecutive j and j + 1 if a[j+1] — a[j] < a[j] — a[1], and if it's true in at least one j then our array is bad if it's always false then our array is good. Hope I understand the hint and explained it correctly.
•  » » » 8 days ago, # ^ | ← Rev. 2 →   +3 Yes after reading above, It became clear that only checking the tuple of the form A_1,A_i and A_(i+1) is sufficient and it will account for all the possible tuples. Also, we can show that if make sure no such tuple exists, then for any subsequence, its difference array will be non-decreasing. Hence all subsequence will be good too.
 » 9 days ago, # |   0 I did read and tried to understand several explenations to C. But still do not get how or why the check "is it possible to invite x persons" works.What is needed to understand that kind of logic?
•  » » 9 days ago, # ^ |   +1 To break it down: We are going to invite X persons, and they are already sorted from poorer to richer from 1 through n We keep a counter of how many we invited until now : cntWhen we are going to the i-th person we check for two things 1. we know we already invited cnt poorer persons (Since all people before i-th are poorer than him) if (b[i] >= cnt) then this condition is fulfilled 2. we know if we invited this person we are going to invite another (X-cnt-1) people (X: total invited, cnt: currently invited, 1: the i-th person himself) if(a[i] >= X-cnt-1) then this condition is fulfilled If both conditions are fulfilled, we invite this person and increase cnt by 1 after going through all n people, if (cnt >= X) then we can invite X peopleHope this helps you
•  » » » 9 days ago, # ^ |   +1 Thanks, I couldn't understand this part from editorial, I really appreciate you helping in the comments.
•  » » » 8 days ago, # ^ |   0 how does selecting a prefix is better than a subsegment of size x from the group. like when do you know when to skip a person as taking him would not be beneficial for the future selections?
•  » » » » 8 days ago, # ^ |   0 When we are checking for valid persons to select we check for both a and b not just one of them, so when we're at the i-th person if he's valid we take him, if we didn't take him we will end up taking another person who's equal to him since the other person will fulfill the same conditions for both a and b.
•  » » » » 8 days ago, # ^ |   0 Look at it like this, If you want to invite $k$ person, then if you wanted to invite a person $x$ as $y$-th poorest in the party, then for a specific $k$ and $x$, the possible $y$-s form a segment, let's say from $l_x$ to $r_x$. After this you can use Monotonic Stack + Lazy (i.e. keep a vector $v$ such that $v_i$ is equal to if we invite $i$ friends, how many more rich person we can add, then add friends one by one and keep $v$ updated in $O(logn)$), hopefully understandable.
•  » » » 8 days ago, # ^ |   0 Ahhhh...ok.Basically we maintain a sorted set of choosen persons, then check in order of richness each single person.We accept that persons if that persons constraints are so that it fits the next free position in the set of choosen persons. Thanks for explaining.
 » 9 days ago, # |   +15 I hope this doesn't get down-voted For problem D, I didn't get the solution proposed above. However, I was thinking of a solution from another angle. Firstly, Odd numbers can can have a sum of 0 by itself so we can have any number of odd numbers in our sequence, Even numbers can have a sum of 0 for sure if there is at least 1 odd number in the sequence since O+E = O. The problem I couldn't figure out, When can E numbers alone (Without any odd number in the sequence) have a sum of 0 I don't know if anyone solved it in this approach, and is it possible this way or the only solution is the one in the editorial?
•  » » 9 days ago, # ^ |   +14 I did solve it in the way you described, and interestingly the answer to your question is the same condition as the editorial arrives at- if you bucket the even numbers by the maximum power of two that divides them, then to create a bad sequence, you need to have an odd number of elements from any one bucket, zero elements from the buckets below it, and any combination from the bucket above.For example, if we have 2, 2, 4, 4, 8, 8, 16, 16, 48We bucket it as follows {2, 2}, {4, 2}, {8, 2}, {16, 3}And the number of bad sequences u can create is -select odd number of 2's and no restriction on other buckets: 2C1 * 2^7select no 2's, odd number of 4's, and no restriction on other buckets: 2C1 * 2*5and so on.Solution: 136657523
•  » » » 9 days ago, # ^ | ← Rev. 2 →   0 Never mind, I get it now. Thanks a lot
•  » » 9 days ago, # ^ |   +7 You can suppose that number 2 means 2x+1, number 4 means 4y+2 and number 6 means 6z+3, your purpose is that you should make their sum equal to zero, you can solve it with Bezout theorem.
•  » » » 9 days ago, # ^ |   0 Thanks a lot
 » 9 days ago, # | ← Rev. 3 →   +40 I have an alternate solution for G without hashing.136722671 lemma 1We will only delete a pair of ( and ) if they are adjacent.So actually we can think of this as deleting any contiguous valid bracket sequence from the string. solutionWe maintain a stack. This stack only stores ( and valid bracket sequences.An example of a stack is [(,(()()),(,()]We process the stack from left to right. When we encounter a (, we just add it to the stack.When we process a ) we will join some suffix of the stack into a valid bracket sequence.For instance, [(,(()()),(,()] becomes [(,(()()),(())]Now, we want to make it in the lexicographical order, so we have to make sure the stack has some monotonic property for the decreasing bracket sequence. For instance, [(),(())] might as well be replaced with [(())]. So when we add a valid bracket sequence, we will pop out some suffix of the stack while the bracket sequence is lexicographically bigger.Well, we can compare 2 strings easily using hashes, but actually we can do it without them :oDefine the potential of the stack as $P$. The potential of the stack is the sum of length of strings in the stack. [(,(()()),(,()] has potential $P=10$.Edit: i have no idea why this is fast but yet i cant find a test which makes the comparisons more than $O(n \log n)$. i dont deserve the AC in contest .-.Now, to join bracket seqeuences, unfortunately I don't have a better method than merging deques in $O(n \log n)$. Perhaps there is a better way? Ive looked at some faster submissions and they seem to use this stack method but only storing the first index of the bracket.
•  » » 9 days ago, # ^ |   +30 My solution 136674351 is a bit different. solutionThe bracket sequence can uniquely be written in the form $) s_1 ) s_2 ) s_3 ) ... s_n ) t_1 ( t_2 ( ... ( t_m,$where each $s_i$ and each $t_i$ are balanced. We never want to remove any parenthesis that is not part of a balanced pair. In the final answer, it is optimal to fully remove each $t_i$.Thus it suffices to solve the original problem for instances for the form $s($ where $s$ is balanced. We can write $s=(u_1)(u_2)...(u_n)$ and recursively assume that we have a minimal solution $u'_i$ for every $u_i$. We then want to select a non-empty subset $m_1,...,m_l$ of $[1..n]$ that leads to a minimal solution $s' = (u'_{m_1})...(u'_{m_l})$.Clearly, $u'_{m_1}$ must be minimal among the $u'_i$. Then $u'_{m_2}$ must be minimal among the $u'_i$ with $i > m_{1}$, and so on.Thus we simply have to sort the strings $u'_i$. Comparing two strings of length $a$ and $b$ in time $O(min(a,b))$ is fast enough, by the same complexity analysis as for the small-to-large trick.
•  » » 9 days ago, # ^ |   +38 My solution uses a similar kind of idea (see 136678450):Lemma 1: We only delete contiguous valid bracket sequences Proof sketchThe subsequence of all deleted brackets is a valid bracket sequence: this is because each prefix contains more ( than ) brackets. Moreover, assume we delete a pair of brackets (). Then, there is a solution where we also delete every bracket in between: if we do not delete such a bracket — say of type ( — in between, then deleting this bracket instead of the originally deleted ( bracket can only make the string lexicographically smaller. Together, these two properties prove the lemma.Then, let's move from right to left and compute the optimal solution for a suffix starting at position $i$. We represent this solution by computing for every $i$ the position $p_i$ of the first bracket contained in the optimal solution for the suffix starting at $i$. Reconstructing the solution for the suffix from the $p_i$ is easy: the first bracket in the solution is at position $p_i$, and the remainder is the optimal solution for the suffix starting at $p_i+1$ (which we can reconstruct recursively).How do we compute $p_i$? If the bracket at position $i$ is ), then $p_i = i$ since we cannot remove this bracket. So, assume that the bracket is (. If there is no matching ) bracket in the string, we will again have $p_i = i$ since we cannot remove this bracket by Lemma 1. So, the only case remaining is that the suffix starting at position $i$ looks like (s)t where s is a valid bracket sequence. Let $j$ be the position where the suffix t starts (which we can compute using a stack).To obtain a solution for the suffix (s)t, there are just two cases: Either we include the first ( bracket, in which case we have to append the optimal solution for the suffix s)t, which is the suffix starting at position $i+1$. Or we delete the first ( bracket, in which case we have to delete the entire substring (s) and we will only keep the optimal solution for the suffix t, which is the suffix starting at position $j$. Since we know the optimal solutions starting at position $i+1$ and $j$, we can simply compare them character by character (using the values $p_i$) to decide which is lexicographically smaller, but this has a runtime of up to $O(n^2)$.Instead, notice that the solution where we keep the first ( bracket looks like (s')t' where s' is some subsequence of s, and t' is the optimal solution for the suffix t. So, we actually ask whether (s')t' is lexicographically smaller than t', and we can already decide this after looking at all characters of (s'): If (s') is not a prefix of t', we know due to our comparisons which string is smaller. If (s') is a prefix of t', I claim that (s')t' is smaller. This is because removing the prefix (s') from t' would also be a valid solution for the suffix t, but must be larger than t' by the optimality of t'. Therefore, it is easy to see that appending another copy of (s') to the beginning of t' will make the string even smaller. I claim that if we use this optimization, the code runs in time $O(n \log n)$. Why is this?The rough idea is as follows: let p[x] be the largest prefix of a bracket string x which has at least as many ( as ) brackets. Then, the comparison from above will consider at most $min(|(s')|, |p[t']|)+1$ characters: this is because every prefix of (s') has at least as many ( as ) brackets. Note that $|(s')| = 2 + |p[s')t']|$ since p[s')t'] = s', so the number of comparisons is at most $min(|p[s')t']|, |p[t']|)+3$.If the optimal suffix is t' and does not contain the brackets from (s'), we can associate the costs the the comparisons with the brackets in (s') since this can happen at most once for any bracket in the string. Otherwise, the optimal suffix is (s')t' and satisfies $|p[(s')t']| \ge |p[s')t']| + |p[t']|$ because p[(s')t'] = (s')p[t'] = (p[s')t'])p[t']. Let x be the smaller of the two strings p[s')t'] and p[t']. Then, the brackets from x are now in an optimal suffix satisfying $|p[(s')t']| \ge 2 |x|$. Since every bracket can be contained in at most $O(\log n)$ many such doubling steps, the total number of comparisons is $O(n \log n)$.
 » 9 days ago, # |   0 Can someone please explain hint 3 in problem D, I can't understand what x is here and how we are arriving at the given equation? Thanks in advance!!
•  » » 9 days ago, # ^ |   +1 I described how to arrive at the equation in the complete solution, it basically means we move the $i$-th sequence, $x_i$ times(i.e. add $x_i$ to all the elements in the $i$-th sequence). If it's possible to find $x_i$-s such that the sum of resulting set of sequences is $0$, then they will satisfy the equation. Also the other way around. (i.e. if it's possible to find such $x_i$-# that the equation holds, then the resulting set of sequences after moving the $i$-th sequence $x_i$ times, satisfies the second property in the statement)
 » 9 days ago, # |   +9 Here are the video Solutions to the first 4 problems of the round in case you prefer that.
•  » » 9 days ago, # ^ |   0 Thank you
 » 9 days ago, # |   +8 problem H was given 2100 rated tag(its a mistake ig). Anyone know how problem rating works.
 » 9 days ago, # |   +8 who can explain the problem D,the solution can't understand。
 » 9 days ago, # |   +10 Thanks for pointing out the typos.
 » 9 days ago, # |   +23 Problem I is just the normal Hackenbush problem on a graph with cycles . You can turn a cycle into a node using "Fusion Principle". And implement it using Heuristic Merging of sets in O(nlog^2) . submission:136731363
 » 9 days ago, # | ← Rev. 2 →   -11 My ideology for the first who have any problem -> as in question we have given that computer hide some cells and on query (suppose k) are done and it will return the k values that will be the distance of hidden cells from the cells that are done by user as querymanhattam formula is important-> |a1-a2| + |b1-b2|; Think YourselfMax value is k==2 (Think yourself) Case 1when n=1 and m=1 this means grid is having just one cells so no query is required by user !! (obviously that will be hidden). Case 2when m==1 or n==1 this means the grid is of only one row || one column in that case only one query means k==1 require as by manhattam formula abs(x2-x1) + abs(y2-y1)=value return by computer when user select some cells and in this case x1==1 or y1==1 depend on grid ,and hence only a single cell query is needed; Case 3if (n and m)!=1 this means now we require at least two equation from formula and hence we take k==2 as user that is two cells (0,0) and n-1,m-1 as both are known from these we can make two equations and can predict the hidden cells .
•  » » 9 days ago, # ^ |   0 For Case 3, we cannot query cells in opposite corners. An example is given in the notes for the problem's test cases. There are multiple cells on the board with the same distance from the opposite corners. We have to query the cells on one side of the board. For example, (0, 0) (0, n-1) or (0, 0) (0, m-1).
 » 9 days ago, # |   +73 .
 » 9 days ago, # | ← Rev. 2 →   0 In problem B, why do we have to find only the minimum i that ai≠an+1−i? What about the next i's where ai != an+1-i? EDIT : I understood why
•  » » 9 days ago, # ^ |   0 If you find the minimum i(say i1) then if you get another i(say i2) after this where ai2 != an+1-i2 then you will check whether you can make it ai2 == an+1-i2 by removing ai2 or an+1-i2 (you can remove ai2 only if ai2 = ai1 or an+1-i2 only if an+1-i2 = ai1). Hope you get it.
•  » » 9 days ago, # ^ |   0 If you find the minimum i(say i1) then if you get another i(say i2) after this where ai2 != an+1-i2 then you will check whether you can make it ai2 == an+1-i2 by removing ai2 or an+1-i2 (you can remove ai2 only if ai2 = ai1 or an+1-i2 only if an+1-i2 = ai1). Hope you got it.
 » 9 days ago, # |   0 Your text to link here... Can anyone tell me what is wrong with this code? I am unable to see the test case in which it is giving WA (Problem B).
 » 9 days ago, # | ← Rev. 2 →   0 First time to solve C in a contest! "A" was weird not gonna lie but for me the contest was very interesting :D
 » 9 days ago, # | ← Rev. 9 →   -35 ..
 » 9 days ago, # | ← Rev. 2 →   -18 .
 » 9 days ago, # |   0 Is there a way to solve problem F using Euler cycle/Euler path idea?
 » 8 days ago, # |   0 can anybody give link/info on why the solution to $x_1.c_1 + x_2.c_2 ... x_n.c_n - \ \sum_{i=1}^{n} c_i.(c_{i - 1} - 1)/2 = 0$ is when $g = gcd(c_1, c_2 ... c_n)$ divides $c_i.(c_{i-1})/2$ as specified on Hint 4 of Problem D
•  » » 8 days ago, # ^ |   0 Search this on google "Linear Diophantine Equation". you will get that.
 » 8 days ago, # | ← Rev. 2 →   0 [deleted]
 » 8 days ago, # | ← Rev. 3 →   -16 Can anyone tell what's wrong with my solution for pro cbblem B ...? 136659778 }
•  » » 8 days ago, # ^ |   0 Brother don't just copy-paste your code in the forum like you have done. No one will read the code above and you will be downvoted like hell. to share your code you can share the submission link of that code, that will be better.
•  » » » 8 days ago, # ^ |   0 Ok, sorry
 » 8 days ago, # |   +3 Otherwise, we remove a black edge, in which case you can show the parity of grundy changes(this one is easy to prove and left for the reader). Have no idea how to prove it, can someone help? Also, how does it help proving that this exact grundy number is not reachable?
 » 8 days ago, # |   0 Hey!!Can anyone please explain some other way to solve B (Can we use 2 pointer approach?).
 » 8 days ago, # |   +6 Can anyone explain the solution of F?? I can not understand the editorial.
 » 8 days ago, # | ← Rev. 4 →   0 So ci(ci−1)/2 has a reminder equal to (2^l) − 1 modulo (2^l). All the other terms ci(ci−1)/2 were divisible by (2^l) except these, so if the number of such ci-s is even, then their reminders sum up to 0 modulo (2^l) then c is good, and not otherwise.Not able to understand this line in editorial of problem D can anybody help?
 » 8 days ago, # |   0 DeadlyCritic if gcd(c1,c2,…,ck)=g, then if g divides s, the array is good, otherwise it's not. Can you explain the prove or just the name of this theoram. I am unable to prove it.
•  » » 7 days ago, # ^ |   0
 » 7 days ago, # |   +31 AliShahali1382 errr.... I think on problem F there seems to be no input with $n,m > 100000$. I submitted a hack with $n=m=300000$ and the validator says $n \leq 100000$. I think the statement has wrong constraints....
•  » » 7 days ago, # ^ |   +3 Oh, damn! Yes, it was supposed to be 100000. It was a mistake in problem statement :(( However, that doesn't affect the solutions.
 » 6 days ago, # | ← Rev. 2 →   -18 The explanation for D looks so complex for a 2000-rated problem
 » 5 days ago, # | ← Rev. 2 →   +3 I'm so shocked the official solution of F is not Euler cycle! solutionFor every (x,y,w), we can add an edge $(x,y)$ if w=1 or $(x+n,y+n)$ otherwise. Then we can find all odd-degree vertex, and the number of them must be even. If x and x+n are both odd-degree, add (x,x+n). Then connect remaining odd vertexes with a virtual vertex. It can be easily seen everyone is even now, and Euler cycle just construct a valid answer.codeBtw, the inspiration comes from this AGC problem