Intimacy between people can be quantified by an inverse relationship with perceived distance. Importantly, this distance perception is asymmetric and directional. For instance, person A might perceive a distance of 1 to person B, while B perceives a distance of 100000 to A. Additionally, distance relationships are transitive: if person A considers B's distance as 2, and B considers C's distance as 1, then A's effective distance to C becomes 3. When multiple paths exist between two individuals, we define the distnace as the minimum among all possible derived distances.

A person's popularity among the opposite gender is determined not by those who feel closest to them, but rather by those who feel most distant. Let Dij represent person i's perceived distance to person j from j's perspective. The "opposite-gender appeal" for person i is calculated as 1 / max{Dji | j ∈ S(i)}, where S(i) contains all individuals of the opposite gender. The "public favorite" within each gender is the person with the highest appeal value, which corresponds to the smallest maximum perceived distance.

Your task is to identify the public favorites from both genders given a set of direct distance relationships.

Input Format

The first line contains a positive integer N (≤ 500), representing the total number of individuals numbered from 1 to N.

Following N lines describe each person's relationships:

Gender K Friend1:Distance1 Friend2:Distance2 ... FriendK:DistanceKThe gender field uses 'F' for female and 'M' for male. K (a non-negative integer less than N) indicates the count of directly known friends. Each friend's ID and the perceived distance to that friend are provided as pairs. All distances are positive integers not exceeding 106.

The input guarantees both genders are represented, no duplicate relationships exist, and no one lists themselves as a friend.

Output Format

Output the IDs of female public favorites on the first line, and male public favorites on the second line. When multiple individuals share the minimum maximum distance, list all IDs in ascending order separated by spaces. No extra spaces should appear at line beginnings or endings.

Solution Approach

The problem requires computing the minimum of the maximum perceived distance from each person to all individuals of the opposite gender. This can be solved using the Floyd-Warshall algorithm in O(n³) time to compute all-pairs shortest paths, accounting for the transitive nature of distance relationships.

Algorithm Steps

1. Initialize an adjacency matrix where matrix[i][j] stores the direct perceived distance from person i to person j. Set unreachable pairs to infinity.
2. Apply the Floyd-Warshall algorithm to compute the minimum perceived distance between every pair of individuals.
3. For each person i, examine all opposite-gender individuals j and update the maximum distance observed from j to i.
4. Identify the minimum maximum distance for each gender and output all IDs achieving this value.

Reference Implementation

<pre>#include <iostream>#include <vector>#include <string>using namespace std;const int MAXN = 510;const int INFINITY = 0x3f3f3f3f;int personCount;int distanceMatrix[MAXN][MAXN];char genderList[MAXN];int maxDistPerPerson[MAXN];void computeAllPairsShortestPath() { for (int k = 1; k <= personCount; ++k) { for (int i = 1; i <= personCount; ++i) { for (int j = 1; j <= personCount; ++j) { if (distanceMatrix[i][k] + distanceMatrix[k][j] < distanceMatrix[i][j]) { distanceMatrix[i][j] = distanceMatrix[i][k] + distanceMatrix[k][j]; } } } }}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); fill(&distanceMatrix[0][0], &distanceMatrix[0][0] + sizeof(distanceMatrix) / sizeof(int), INFINITY); cin >> personCount; for (int i = 1; i <= personCount; ++i) { int friendCount; cin >> genderList[i] >> friendCount; for (int t = 0; t < friendCount; ++t) { int friendId, distValue; char colon; cin >> friendId >> colon >> distValue; distanceMatrix[i][friendId] = distValue; } } computeAllPairsShortestPath(); fill(maxDistPerPerson, maxDistPerPerson + MAXN, 0); for (int i = 1; i <= personCount; ++i) { for (int j = 1; j <= personCount; ++j) { if (genderList[i] != genderList[j]) { maxDistPerPerson[j] = max(maxDistPerPerson[j], distanceMatrix[i][j]); } } } int bestFemale = INFINITY; int bestMale = INFINITY; for (int i = 1; i <= personCount; ++i) { if (genderList[i] == 'F') { bestFemale = min(bestFemale, maxDistPerPerson[i]); } else { bestMale = min(bestMale, maxDistPerPerson[i]); } } bool firstOutput = true; for (int i = 1; i <= personCount; ++i) { if (genderList[i] == 'F' && maxDistPerPerson[i] == bestFemale) { if (!firstOutput) cout << ' '; cout << i; firstOutput = false; } } cout << '\n'; firstOutput = true; for (int i = 1; i <= personCount; ++i) { if (genderList[i] == 'M' && maxDistPerPerson[i] == bestMale) { if (!firstOutput) cout << ' '; cout << i; firstOutput = false; } } cout << '\n'; return 0;}</pre>### Complexity Analysis

The Floyd-Warshall algorithm dominates the runtime with O(n³) time complexity, where n ≤ 500. Space usage is O(n²) for storing the distance matrix. This solution efficiently handles the transitive distance computation required by the problem.