CAGES  Lights, Snakes and Cages
In the zoo there are N cages in which we keep N snakes: each snake in its cage. For experimental reasons, in a month we will move each snake to a different cage: this reordering is given in the input.
Each cage is illuminated by special light, which may be of type A, type B or type C. Your task is to assign the lights A, B, C to the cages so that:
1) each snake will change its lighting, i.e. it will be moved to the cage illuminated differently from the cage it currently inhabits;
2) lightings are equally distributed, i.e. the number of cages A, the number of cages B and the number of cages C differ by at most one.
Input
The first line contains an integer N (2 ≤ N ≤ 300 000), the number of snakes and cages. Cages are numbered from 1 to N.
Each of the next N lines contains an integer. When Kth of these lines contains the number L, it means that the snake from the cage K will be moved to the cage L (K ≠ L). Two snakes will not move to the same cage.
Output
Print the string composed of the characters A, B and C, such that the Kth character denotes the lighting of the cage K.
If there are multiple solutions, print any.
Example
Input: 4
4
3
2
1
Output: ACBC
hide comments
daedaldan:
20200114 00:09:14
@joe85123 @harish_49 @psetter Would you mind sending me your solution at daniel22373@gmail.com? I've working on this one, and I want a hint or two to push me in the right direction. Thanks! 

harish_49:
20190923 11:19:25
AC in 1 go 

itssanat:
20190330 10:19:15
nice problem:) 

joe85123:
20180711 17:34:11
Really nice problem! Finally AC after so many tries Last edit: 20191118 17:59:57 

khoaph:
20180630 10:12:33
Oh my pretty code but got TLE 

drexter:
20180412 18:05:34
@psetter please check my code having id : 21512185..i am getting wrong answer after 15 test cases 

soham_12345:
20170719 22:18:39
Can anyone tell me where I am going wrong? Submission id : 19827082 .. I used a simple dfs 

shanku_iiith:
20161013 15:41:13
Last edit: 20161013 22:57:40 

mohitsinghdz:
20160930 11:30:28
the reason this problem cant be solved is snakes,


aeon:
20160917 23:00:58
@psetter Kindly have a look at my solution ( id : 17732677 ), I have considered even the cyclic cases, but still I am getting WA after 15 test cases. 
Added by:  Adrian Satja Kurdija 
Date:  20140324 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Croatia nationals 2014 (6th grade, 3rd problem "Zmije") 