 Let $n$ be an integer greater than $1$, and let $p$ be a prime divisor of $n$. A confederation consists of $p$ states, each of which has exactly $n$ airports. There are $p$ air companies operating interstate flights only such that every two airports in different states are joined by a direct (two-way) flight operated by one of these companies. Determine the maximal integer $N$ satisfying the following condition: In every such confederation it is possible to choose one of the $p$ air companies and $N$ of the $np$ airports such that one may travel (not necessarily directly) from any one of the $N$ chosen airports to any other such only by flights operated by the chosen air company.

Switch to graph theoretical notation: a \( p \)-partite complete graph \( K_{n,n,\ldots,n} \) has its edges colored in \( p \) distinct colors. We need to determine the minimal size of the largest connected component in the color subgraphs \( G_i \), \( i=1,2,\ldots,p \).

We claim the required size is \( n \). The problem naturally splits into two parts:

1. **Any coloring of the big graph generates a unicolored connected component on \( n \) vertices.**

   Assume there is a coloring that does not generate such a component. Consider the color which is used the most; assume it is color 1. The big graph has exactly \(\frac{n^2p(p-1)}{2}\) edges. Then \( G_1 \) has at least \(\frac{n^2(p-1)}{2}\) edges.

   Now split \( G_1 \) into connected components; say there are \( k \) of them. Then none of them has more than \( n-1 \) vertices, from which \( k > p \). Let's say these components have size \( x_i \le n-1, i=1,2,\ldots,k \) with \(\sum x_i = np\). Since the big graph was \( p \)-partite, so is \( G_1 \). Apply then Turán's theorem (no \( p+1 \) cliques) on each of the \( k \) connected components to get that the total number of edges in the connected components, and consequently the total number of edges in \( G_1 \), does not exceed \(\frac{p-1}{2p}\sum x_i^2\).

   We now have lower and upper bounds for the number of edges in \( G_1 \):
   \[
   \frac{n^2(p-1)}{2} \le \frac{p-1}{2p}\sum x_i^2
   \]
   Simplifying, we get:
   \[
   \sum x_i^2 \ge pn^2
   \]
   But Karamata's inequality applied to the strictly convex function \( x^2 \) and the \( k \)-tuplets \((n,n,\ldots,n,0,0,\ldots,0)\) and \((x_1,x_2,\ldots,x_k)\) implies exactly the opposite inequality, leading to a contradiction.

2. **There exists a graph for which the largest connected component is of size exactly \( n \).**

   For this, we group all \( n \) vertices on a shore in \( p \) equisized groups. Now take group \( i \) from shore \( k \) and group \( j \) from shore \( l \). We color the edges between the two groups in the color which is equal to \( 1 + (j-i)(l-k)^{-1} \) in \( \mathbb{Z}_p \). It is readily checkable that each color graph \( G_i \) contains exactly \( p \) size-\( n \) connected components of the form \( K_{d,d,\ldots,d} \), where \( d = \frac{n}{p} \), so the example is correct, and we are done.

\(\blacksquare\)

The final answer is \( \boxed{ n } \).