1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# include <cstdio>
# include <algorithm>
# include <string>

const short int MAX_N = 302;
const short int MAX_M = 402;


struct node {
  short int in_total = 0;
  short int out_total = 0;
  short int in[ MAX_N ];
  short int out[ MAX_N ];
};


inline short int max( short int a, short int b ) {
  return ( a > b ) ? a : b;
}

inline short int min( short int a, short int b ) {
  return ( a < b ) ? a : b;
}


short int evaluate_graph( node graph[ ], short int n, std::string removed ) {
  short int longest_path = 0;
  short int longest_in[ MAX_N ];
  for ( short int i = 1; i <= n; i ++ ) {
    longest_in[ i ] = 1;
  }
  
  node * current_node;
  for ( short int node_number = 1; node_number <= n; node_number ++ ) {
    if ( removed[ node_number - 1] ) {
      continue;
    }
    current_node = & graph[ node_number ];
    for ( short int in_index = 0; in_index < current_node->in_total; in_index ++ ) {
      short int neighbour_index = current_node->in[ in_index ];
      if ( removed[ neighbour_index - 1] ) {
        continue;
      }
      short int path_len = longest_in[ neighbour_index ] + 1;
      longest_in[ node_number ] = max( longest_in[ node_number ], path_len );
    }
    longest_path = max( longest_in[ node_number ], longest_path );
  }
  return longest_path;
}


int main() {
  short int n, m, k;
  node graph[ MAX_N ];
  scanf( "%hd %hd %hd", & n, & m, & k );
  for ( short int i = 0; i < m; i ++ ) {
    short int x, y;
    scanf( "%hd %hd", & x, & y );
    graph[ x ].out[ graph[ x ].out_total ] = y;
    graph[ x ].out_total ++;
    graph[ y ].in[ graph[ y ].in_total ] = x;
    graph[ y ].in_total ++;
  }
  short int result = MAX_N;
  std::string removed_bitmask( k, 1 );
  removed_bitmask.resize( n, 0 );
  do {
    short int perm_result = evaluate_graph( graph, n, removed_bitmask );
    result = min( perm_result, result );
  } while ( std::prev_permutation( removed_bitmask.begin(), removed_bitmask.end() ) );
  
  

  printf( "%hd", result );

  return 0;
}