# CFR 316 B2. EKG ( DP )

Problem - 316B2 - Codeforces

The first line contains two integers n (1 ≤ n ≤ 1e3) and x (1 ≤ x ≤ n) — the number of beavers that stand in the queue and the Smart Beaver's number, correspondingly. All willing to get to the doctor are numbered from 1 to n.
The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ n) — the number of the beaver followed by the i-th beaver. If ai = 0, then the i-th beaver doesn't know who is should be in front of him. It is guaranteed that values ai are correct. That is there is no cycles in the dependencies. And any beaver is followed by at most one beaver in the queue.
TL: 500 ms
ML: 256 MB

O( N^2 )

```int N, M;
vi A;

void init(){
cin >> N >> M; --M;
A = vi( N );
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
--A[ i ];
}
}

vi front;
vi back;
vvi dp;

int mpos = -1;
vi other_size;

void solve(){
front = back = vi( N, -1 );
for( int i = 0; i < N; ++i ){
front[ i ] = A[ i ];
}
for( int i = 0; i < N; ++i ){
if( front[ i ] == -1 ) continue;
back[ front[ i ] ] = i;
}
for( int i = 0; i < N; ++i ){
static vi vis( N );
if( vis[ i ] ) continue;
int u = i;
while( front[ u ] != -1 ){
u = front[ u ];
}
int size = 0;
int found_m = 0;
while( true ){
vis[ u ] = 1;
if( u == M ){
found_m = 1;
mpos = size;
}
++size;
if( back[ u ] == -1 ){
break;
}
u = back[ u ];
}
if( found_m ) continue;
other_size.emplace_back( size );
}
dp = vvi( other_size.size() + 1, vi( N ) );
dp[ 0 ][ 0 ] = 1;
for( int i = 0; i < other_size.size(); ++i ){
for( int j = 0; j < N; ++j ){
if( dp[ i ][ j ] == 0 ) continue;
dp[ i + 1 ][ j ] |= dp[ i ][ j ];
dp[ i + 1 ][ j + other_size[ i ] ] |= dp[ i ][ j ];
}
}
for( int i = 0; i < N; ++i ){
if( dp[ other_size.size() ][ i ] == 0 ) continue;
cout << i + mpos + 1 << endl;
}
}
```